Les limites d'exécution dans P sont-elles décidables? (réponse: non)

64

La question posée est de savoir si la question suivante est décidable:

Problème   Étant donné un entier et que la machine de Turing trouverait dans P, le temps d’exécution de par rapport à la longueur en entrée ?M M O ( n k ) nkMM O(nk)n

Une réponse étroite de «oui», «non» ou «ouverte» est acceptable (avec références, esquisse de preuve ou revue des connaissances actuelles), mais des réponses plus larges sont également les bienvenues.

Répondre

Emanuele Viola a publié une preuve que la question est indécidable (voir ci-dessous).

Contexte

Pour moi, cette question s'est posée naturellement en analysant la réponse de Luca Tevisan à la question. Les temps d'exécution pour P nécessitent-ils des ressources EXP au maximum ? … Est-ce que des exemples concrets sont connus?

La question concerne également une question de MathOverflow: Quels sont les problèmes les plus attrayants de Turing en mathématiques? , dans une variante dans laquelle le mot "mathématiques" est remplacé par "ingénierie", reconnaissant que l'estimation de l'exécution est un problème d'ingénierie omniprésent associé à (par exemple) la théorie de commande et la conception de circuits.

Ainsi, l’objectif général de cette question est de mieux comprendre quels sont les aspects pratiques de l’estimation à la volée de la classe de complexité P qui sont réalisables (c’est-à-dire qui nécessitent des ressources de calcul dans P pour estimer), par opposition à ceux qui sont irréalisables (c.-à-d. nécessite des ressources de calcul en EXP pour estimer), par opposition à formellement indécidable.

--- modifier (post-réponse) ---

J'ai ajouté le théorème de Viola au wiki de communauté de MathOverflow "Des problèmes attrayants de Turing-indécidables". C'est la première contribution de ce wiki associée à la classe de complexité P; cela témoigne de la nouveauté, de la naturalité et de la vaste portée du théorème de Viola (et de sa beauté aussi).

--- modifier (post-réponse) ---

La monographie de Juris Hartmanis Les calculs réalisables et les propriétés de complexité prouvables (1978) couvrent une grande partie du même matériau que la preuve d'Emanuele Viola.

John Sidles
la source
En réponse aux questions posées sur le blog de Lance Fortnow et Bill GASARCH, sous le thème "75 ans d’informatique", commençant par "j’ai souvent souhaité que Turing pose sobrement:" Quels sont les processus vérifiables pouvant être appliqués à numéro? "... au lieu que Turing pose la question plus difficile:" Quels sont les processus possibles permettant de calculer un nombre? ", la question suivante sera (environ)" Existe-t-il des machines de Turing qui dans NP, dont l'appartenance à P est indécidable? "C'est pour montrer que j'y pense encore! :)
John Sidles
2
Bien que la preuve de I Emanuele Viola soit plus claire, une question très similaire a été posée et répondue sur Mathoverflow: mathoverflow.net/questions/28056/…
Alex ten Brink
Plusieurs réponses et idées sur ce fil se sont révélées pertinentes pour un essai / une série de questions que Dick Lipton a publiées sur son blog, La lettre perdue de Godel ; cet essai / ensemble de questions est "Mise en place avec P = NP". URL: rjlipton.wordpress.com/2011/07/04/getting-on-base-with-pnp
John Sidles
Bien que les limites dans P soient indécidables, cela n'empêche pas d'essayer (en se limitant davantage). Un exemple si donné dans cette réponse de mémoire
Artem Kaznatcheev
1
Cette question a inspiré l'article suivant: arxiv.org/abs/1307.3648
David G

Réponses:

83

Le problème est indécidable. Plus précisément, vous pouvez réduire le problème d’arrêt comme suit. Soit une instance du problème d’arrêt, construisons une nouvelle machine qui fonctionne comme suit: sur des entrées de longueur , elle simule sur pour étapes. Si accepte, bouclez pendant étapes et arrêtez; sinon, bouclez pendant étapes et arrêtez-vous.M ' n M x n M n 2 n 3(M,x)MnMxnMn2n3

Si s'arrête sur il le fait en étapes , de sorte que le temps d'exécution de est à . Si ne s’arrête jamais, le temps d’exécution de est d’au moins .x t = O ( 1 ) M ' O ( n 2 ) M M ' n 3Mxt=O(1)MO(n2)MMn3

Par conséquent, vous pouvez décider si accepte en décidant si le temps d'exécution de est ou .x M ' O ( n 2 ) O ( n 3 )MxMO(n2)O(n3)

Manu
la source
4
pourquoi M doit-il s’arrêter sur x (si c’est le cas) en étapes O (1)?
Suresh Venkat
10
x nM et sont fixes indépendamment de . xn
Manu
2
Preuve très astucieuse, s'agit-il d'une variante d'un résultat connu ou vous venez de le concevoir?
Antonio E. Porreca
3
@Raphael: C'est un domaine délicat, que je ne pense pas avoir résolu. Certains sites stackexchange encouragent la modification des réponses des autres. Nous n'avons pas de politique contre cela, mais, dans la pratique, je n'ai presque jamais vu cela se faire. Un point technique: si une réponse est trop modifiée, elle devient un wiki de communauté et @Emanuele n’obtiendra plus de points de représentation si sa réponse était votée par la suite. Je pense que des explications supplémentaires aideraient à clarifier: @John Sidles pensait au départ que la promesse n'était pas utilisée, mais la preuve utilise une promesse plus forte : court en ou , pas seulement P.n 2 n 3Mn2n3
Aaron Sterling,
2
@ John: Tant qu'aucune référence publiée n'est donnée, tenez compte de cette recommandation .
Raphaël
29

Il s'agit d'une reformulation de la réponse d'Emanuele Viola dans le but d'être plus compréhensible.

Nous montrons que le problème donné est indécidable en réduisant le problème de l' arrêt général lui.HPH

Soit un cas quelconque du problème d’arrêt, c’est-à-dire qu’il faut décider si ( s’arrête sur ). Construisez une machine de Turing qui fonctionne comme suit:M ( x ) M x M *(M,x)M(x)MxM

M*(y) = {
  n := |y|
  Simulate M(x) for n steps
  if ( M(x) has halted )
    Execute n*n arbitrary steps
  else
    Execute n*n*n arbitrary steps
}

Nous observons maintenant les implications suivantes:

M(x)n0N:M halts on x after at most n0 stepsy:nn0M(y) executes n2 arbitrary stepsTM(n)O(n2)

et

M(x)nN:M does not halt on x in less than n stepsy:M(y) executes n3 arbitrary stepsTM(n)Ω(n3)

Par conséquent, . En supposant que était décidable par algorithme, il en serait de même pour , ce qui donne une contradiction. P H H(M,x)P(M,2)PH

Raphaël
la source
12

Du côté positif, il est décidable de savoir si une machine Turing à bande unique fonctionne dans le temps pour , voir:nCn+DC,DN

David Gajser: Vérification du fonctionnement des machines Turing non déterministes à bande unique dans le tempsCn+D , arXiv: 1312.0496

Andrej Bauer
la source
1
Pas de pénurie de comportement inhabituel chez les petits monothérapeutes à bande unique. :)
Kaveh
4

Le problème a également été résolu dans mon article " Le contenu intensif du théorème de Rice " POPL'2008, où je prouve qu'aucune "clique de la complexité" n'est décidable. Une clique de la complexité est une classe de programmes fermés par des programmes ayant un comportement et une complexité similaires . Je fournit également les conditions nécessaires pour les propriétés semi-décidables.

Les programmes en cours d'exécution dans O (n ^ k) sont une clique de complexité dans le sens ci-dessus, donc l'ensemble n'est pas décidable.

Le résultat a également été récemment étendu aux paramètres subrécursifs (tels que P) de Mathieu Hoyrup: Les propriétés décidables des fonctions subrécursives (ICALP 2016).

Andrea Asperti
la source
2

Pour ajouter aux réponses précédentes, ce problème est non seulement indécidable, mais complet. Ainsi, il est indécidable même si le décideur a un oracle pour résoudre le problème. Σ20

Pour clarifier l'exhaustivité, bien que la condition de promesse de temps P soit également , il existe un ensemble de codes décidables tels que toutes les machines de soient des polynômes et que la question soit compléter le .Σ20SSO(n2)Σ20S

Pour le prouver, choisir un complète , avec temps polynomial (pour les nombres binaires).Σ20φφ(x)kmψ(x,k,m)ψ

Alors est valable si la machine suivante est où est la longueur entrée (la machine ne se préoccupe que de la longueur entrée):φ(x)O(n2)n

pour dans 0 à :     si : # testé à l'aide d'une boucle d'         arrêt,     attendez étapes d' arrêtn m < nkn
n 2m<nψ(x,k,m)

n2

Notez que pour chaque pas trop petit , si un programme s'arrête toujours (par exemple), étapes est complet, mais poser des questions sur les limites de manière robuste donne .n 2 + c Π 0 1 Σ 0 2cn2+cΠ10Σ20

Dmytro Taranovsky
la source
-1

voici de nouvelles analyses / angles / résultats plus systématiques récents sur cette question et les questions connexes, introduisant le concept de "vérifiabilité algorithmique" et un analogue de Rice similaire à la théorie de la complexité. une section pertinente de l’abrégé est donnée ci-après et il existe de nombreux autres théorèmes liés à la prouvabilité de P vs NP, etc.

  • Pourquoi le concept de complexité informatique est difficile en mathématiques vérifiables / Hromkovic

    Premièrement, nous prouvons le théorème d'inviolabilité de Rice, affirmant que chaque problème sémantique non trivial concernant les programmes n'est pas presque partout résolvable par la "mathématique" vérifiable par algorithme. En utilisant cela, nous montrons qu'il existe une infinité d'algorithmes (programmes qui sont des algorithmes prouvables) pour lesquels il n'existe pas de preuve qu'ils fonctionnent en temps polynomial ou qu'ils ne fonctionnent pas en temps polynomial. ...

    Notez que, si P! = NP est prouvable en AV-mathématiques, alors pour chaque algorithme A, il est prouvable que "A ne résout pas SATISFIABILITY ou A ne fonctionne pas en temps polynomial". Fait intéressant, nous montrons enfin qu'il existe des algorithmes pour lesquels il n'est pas prouvé qu'ils ne fonctionnent pas en temps polynomial, ni qu'ils ne résolvent pas SATISFIABILITÉ. De plus, il existe un algorithme résolvant SATISFIABILITÉ pour lequel on ne peut pas prouver en mathématique AV qu’il ne fonctionne pas en temps polynomial.

    De plus, nous montrons que P = NP implique l’existence d’algorithmes X pour lesquels la revendication "X résout la SATISFIABILITÉ en temps polynomial" n’est pas prouvable en mathématiques AV.

vzn
la source
-3

La solution de Viola peut être généralisée à n’importe quel temps de fonctionnement (au-delà de poly): Vous pouvez y réduire le problème d’arrêt de la manière suivante. Soit une instance (M, x) du problème d’arrêt, construisons une nouvelle machine M ’qui fonctionne comme suit: sur des entrées de longueur n, elle simule M sur x pour f (n) étapes ou jusqu’à ce que M s’arrête, où f (n ) est une fonction croissante arbitraire (supérieure à constante) de n. (Obs .: M 'lit l'entrée progressivement pour éviter de perdre du temps linéaire [O (n)] juste pour lire inutilement toute l'entrée si elle est assez grande et que M s'arrête.)

Si M s’arrête sur x, il le fait par pas de T = O (1), de sorte que le temps d’exécution de M ′ serait de 0 (1). Si M ne s’arrête jamais, le temps d’exécution de M ′ est O (n ^ 2 * f (n)).

Par conséquent, vous pouvez décider si M accepte x en décidant si le temps d’exécution de M ’est O (1) ou O (n ^ 2 * f (n)).

Ensuite, le code auxiliaire de Raphaël peut être généralisé en conséquence par:

Soit (M, x) une instance du problème d’arrêt, c’est-à-dire qu’il faut décider si M s’arrête sur x. Construisez une machine de Turing déterministe (DTM) M * qui fonctionne comme suit:

  1. M * (entrée) = {
  2. n: = 0
  3. Lire le premier symbole de l'entrée
  4. Boucle:
  5. n: = n + 1
  6. Simulez M (x) pour des pas f (n) ou jusqu'à ce que M (x) s'arrête
  7. Lire le prochain symbole de l'entrée
  8. Boucle jusqu'à end_of_put ou jusqu'à ce que M (x) soit arrêté
  9. }

Nous observons maintenant les implications suivantes:

M s'arrête sur x après au plus k étapes (constantes) => T (M *) = O (1) et

M ne s’arrête jamais sur x => T (M *) = O (n ^ 2 * f (n))

Par conséquent, même décider si le temps d'exécution d'un DTM arbitraire est simplement plus grand que constant est aussi difficile que Halting Problem. □

André Luiz Barbosa
la source
2
1) S'il vous plaît utiliser LaTeX. 2) Quelle est la nouvelle contribution à cette question? 3) Votre raisonnement est défectueux. La simulation de prend du temps déjà, pour que ne puisse certainement pas fonctionner en temps constant. O ( n ) M *MO(n)M
Raphaël,
Pour n assez grand, si M (x) s'arrête, sa simulation s'arrête aussi et revient à M * entre n0 (constants) pas.
André Luiz Barbosa