J'aime savoir s'il est possible de "écrire un programme entrée: Tout programme (P) [dans n'importe quelle langue ou d'une langue particulière]
Sortie: Complexité du temps de ce programme (P).
Y a-t-il eu des tentatives préalables pour écrire un tel programme?
Y a-t-il des algorithmes disponibles à cet effet?
Si oui, veuillez fournir les liens, les références nécessaires ou avec tout type de guidage possible.
4 Réponses :
non. Ce n'est pas possible. Ceci est une forme de Halte Problème.
+1: jusqu'à ce que vous puissiez prouver que le programme P est arrêté, vous ne pouvez rien prouver à propos de la complexité du temps.
Mais pour une langue complète non turicing, il pourrait être possible :) (et c'est une question ouverte à quel point ces langues pourraient être utiles)
Ignorer les BS théoriques sur le problème d'arrêt. Il semblerait que vous puissiez faire un programme qui vous donnerait une estimation approximative et supposez simplement que le programme finisse par finir.
@CoryMatthews: Non. Vous ne pouvez pas obtenir une "estimation approximative". Vous avez soit un programme que vous pouvez discuter pour la complexité - comme un exercice mathématique - et avoir raison. Ou vous avez un programme que vous ne pouvez pas prouver des terminaux; auquel cas vous ne pouvez rien faire de plus.
Si le programme de Cory existait, alors même si cela ne fonctionnait que pour des problèmes connus pour s'arrêter, il résoudrait que l'irritant de la question P = NP une fois pour toutes. Il suffit de l'exécuter contre «Essayez chaque programme qui existe dans l'algorithme pseudo-parallèle» pour le problème du vendeur itinérant, et déterminez si cela a une complexité polynomiale. Si oui, p = np, sinon p! = Np. Depuis p = np n'est pas résolu, aucun programme de ce type n'existe.
@Stevejessop: Vous avez tort, votre méthode ne pouvait pas décider P = NP, principalement parce qu'il existe infiniment de nombreux programmes.
@jpalacek: Je parle d'un programme dont l'entrée est une instance de TSP, et qui explique chaque programme qui existe (dont il existe de manière de manière de beaucoup de nombreuses personnes) et teste le résultat de chacun (au fur et à mesure de la fin, si elle fait) pour voir si cela résout cette instance de TSP. Il y a plus d'une façon d'écrire ce programme, mais tous ont la propriété qu'ils ont une complexité polynomiale si et seulement si p = np. Donc, si l'oracle de Cory existe, voyez ce que «estimation approximative» donne pour un tel programme, et vous avez une "estimation approximative" de savoir si p = np. Tout ce qui signifie "estimation approximative".
Tout autre problème complet de NP serait à la place du TSP, bien sûr - la version de décision de TSP est NP-complète. L'ensemble du point de la technique de la cavernation consiste à exécuter de manière de manière comptablement de nombreux programmes "en parallèle" sur une machine déterministe. Notez que toute ma proposition tombe carrément sous la direction de "BS théoriques sur le problème d'arrêt" que Cory se distingue - il ne propose pas sérieusement un test infaillible, je souligne simplement comment je sais qu'aucun test infaillible n'est connu. .
Cela n'a rien à faire avec le problème d'arrêt, où la décision le sous-programme doit être en mesure de faire référence à l'ensemble du programme qui doit pouvoir utiliser / se référer au sous-programme de décision ( Ce n'est qu'alors que le programme de dégénération paradoxal peut être construit prouvant l'impossibilité du sous-programme de décision d'arrêt). Ici, la décision Programme est entièrement extraite au programme analysé qui ne sait même pas le programme de décision, beaucoup moins en mesure de se référer à cela.
Prouvage La complexité d'un algorithme arbitraire n'est pas possible, mais vous pouvez en principe l'estimer:
Il y a un nombre quelconque de pièges à cette approche p>
Il existe de nombreuses façons que cette approche puisse être dupe à moins que vous n'utilisez d'énormes valeurs de n. Par exemple, cet algorithme ressemblera à O (1) à moins que vous n'utilisiez astronomique valeurs pour n p>
sleep for 10 days run an O(n log(n)) sorting algorithm
Le problème est l'étape 3: vous ne pouvez pas être certain que le programme jamais s'arrête pour une entrée arbitraire. C'est le problème d'arrêt. La conséquence est que même cette méthode d'estimation ne produira pas, en général, une mesure utile.
Pire, il y a des algorithmes de terminaison qui prendront toujours jusqu'à la mort de la chaleur de l'univers pour produire leur réponse. Vous devriez probablement le savoir avant de commencer à essayer de l'exécuter et de rassembler des données.
Vrai, mais si vous aviez une tolérance, max t (n) max t (n) la méthode pourrait être utilisée pour rendre l'estimation des fois moins que T (n) (juste force tuer le processus après max t (n) temps). Cela ne vous dira pas si le programme s'arrêtera, mais vous découvrirez la durée de fonctionnement de l'algorithme d'obtenir le résultat de «Ce programme fonctionne si longtemps qu'il est efficacement utilisable pour moi».
Je ne dirais pas que ce n'est pas utile en général. La plupart des algorithmes que vous souhaitez indiquer seront arrêtés tritiquement. Comme Mobrule l'a souligné, cela ne prouve rien sur les runtimes, mais cela fournit un test statistique utile.
Et pour des raisons pratiques, le comportement asymptotique est en tout cas complètement, totalement non pertinent. Je n'ai littéralement jamais écrit de programme dans lequel je me soucie de son exécution si ce temps d'exécution dépasse un an et une année à court terme de la limite que n tendue à l'infini. Si votre soi-disant algorithme n'arriver pas pour certaines entrées, vous avez des problèmes que vous ne pouvez pas mesurer sa complexité apparente (pour la petite N) par cette méthode ...
Le comportement asymptotique empirique local est une mesure d'extrapolation utile pour le temps d'exécution et assez facile pour trouver comme k = journal (t2 / t1) / journal (n2 / n1) pour local o (n ^ k) Comportement (pris en tant que temps d'exécution T1, T2 à Problème Tailles N1, N2 ).
Eh bien, je pense que vous faites cela en supposant tous les cas. 1: comme pour la première fois un module pouvant extraire chacune des instructions 2: Faites une base de données d'instructions pour correspondre à l'instruction de programme. 3: Calculez la complexité en récupérant la complexité de temps appropriée définie par vous dans la base de données et c'est tout.
Ne pouvons-nous pas introduire de plus de variables dans l'algorithme lui-même et trouver la complexité de la même manière que nous le faisons manuellement. Comme par exemple, nous pouvons avoir une variable dans un tri d'insertion, dites n = 0 qui conserve la piste de toute la partie de boucle de l'algorithme puis donner la réponse sous O (n ^ 2)
Vous devez toujours l'exécuter sur de nombreux intrants différents. Il s'agit d'auto-observateur au lieu de vous calculer manuellement les moyennes ne changent pas que fait. Mais si votre routine vit à l'intérieur d'une sorte de système dynamique qui est constamment utilisée, alors oui, l'auto-observation / la conscience est une très bonne idée, imo. La partie superviseure une partie d'un système observerait et détecterait quelles parties nécessitent des améliorations et choisissent un autre algorithme.
SIMILIAIRE À CE POST Stackoverflow.com / Questions / 480775 / ...
Et Stackoverflow.com/Questtions/7331801/...