Les attributs indécidables de P entravent-ils la décision de P par rapport à NP? (réponse: peut-être)

Cinq questions liées sont posées, et une seule réponse intégrée est espérée:

• Q1: Existe-t-il des langues $L$ reconnues uniquement par ces machines Turing $P$ dontles exposants d'exécution sont indécidables?
• Q2: Des exemples de ces machines de Turing peuvent-ils être finement construits?
• Q3: Ces machines de Turing peuvent-elles être instanciées concrètement? ( par exemple , par des oracles qui les "devinent" plutôt que de les construire de façon définitive).
• Q4: Quels autres attributs de P (outre les exposants d'exécution) sont actuellement connus pour être indécidables? Pour quels attributs de$P$ cette question est-elle ouverte?
• Q5: Les attributs indécidables de $P$ font-ils obstacle à la décidabilité de $P \ne NP$ ?

Notez soigneusement le mot «uniquement» dans Q1 (qui exclut la réponse suggérée de Lance Fortnow).

Conclusions et conversion en wiki communautaire

• La question posée, "Les attributs indécidables de P entravent-ils la décision de P par rapport à NP?", Est ouverte et considérée comme difficile, tout comme de nombreuses questions spécifiques (comme Q1–4 ci-dessus) qui lui sont naturellement associées.

• La monographie de Juris Hartmanis, 1978, Calculs réalisables et propriétés de complexité prouvables fournit une bonne entrée dans la littérature et (apparemment) il n'y a pas eu de revue publiée depuis Hartmanis.

• Cette classe de questions est suffisamment inexplorée pour que le défi de trouver des preuves rigoureuses soit intimement mêlé au défi de choisir de bonnes définitions de départ.

• Les remarques réfléchies et les croquis de preuve perspicaces fournis par Travis Service et Alex ten Brink sont reconnus et appréciés.

Étant donné que la question est ouverte et qu'elle est discutée sur plusieurs fils de discussion de blog mathématique ( 1 , 2 , 3 , 4 , 5 , 6 ), cette question a été signalée pour la conversion en wiki communautaire.

Mise à jour II et résumé

Je me rends compte que la monographie de Juris Harmanis, 1978, Calculs réalisables et propriétés de complexité prouvée peut être lue comme une réponse approfondie au premier trimestre de 2015 . De plus, les (excellents) croquis de preuve Q1 et Q4 fournis ci-dessous par Travis Service et par Alex ten Brink fournissent une affirmation et une extension modernes des conclusions générales de Hartmanis:

Les résultats sur la complexité des calculs changent radicalement si l'on considère uniquement les propriétés des calculs qui peuvent être prouvées formellement (souligné par Hartmanis) ...

Ainsi, nous devons nous attendre à ce que les résultats sur l'optimalité de tous les programmes calculant la même fonction qu'un programme donné diffèrent des résultats d'optimalité sur tous les programmes qui peuvent être formellement prouvés comme équivalents au programme donné. ...

Nous [devrions] envisager la possibilité que ce fameux problème [ $P\overset{?}{=}NP$ ] peut ne pas être résoluble dans une théorie mathématique formalisée, telle que la théorie des ensembles.

Il ressort clairement de la monographie de Hartmanis et des réponses fournies par Travis et Alex que Q1–5 sont considérablement au-delà de l'état actuel de la technique de la théorie de la complexité. De plus, ces questions / réponses sont évidemment suffisamment subtiles pour nécessiter des ajustements de définition minutieux et justifier des expositions de longueur de monographie… ce qui, je l'espère, ne découragera pas les gens de publier d'autres réponses. :)

Pour plus de détails techniques, voir la réponse de Joel David Hamkins sur MathOverflow à la question Un problème peut-il être à la fois polynomial et indécidable? (recommandé par Alex ten Brink).

Si dans la monographie de Hartmanis on remplace par «calcul des fonctions» l'expression «simulation de la dynamique», le résultat peut être lu comme un traité sur les limites théoriques de la complexité de l'ingénierie des systèmes… c'est la raison pratique pour laquelle nous, ingénieurs, nous soucions de ces problèmes.

Une opinion opposée à celle de Hartmanis a récemment été exprimée par Oded Goldreich dans une lettre à l'éditeur du CACM intitulée "On Computational Complexity" :

Malheureusement, nous manquons actuellement de bonnes réponses théoriques aux questions les plus naturelles concernant le calcul efficace. Ce n'est pas le cas parce que nous posons les mauvaises questions, mais plutôt parce que ces questions sont très difficiles.

Il est (bien sûr) parfaitement concevable que les opinions de Hartmanis et de Goldreich se révéleront correctes, par exemple, une preuve formelle de l'indécidabilité de la séparabilité du PvsNP pourrait raisonnablement être considérée comme validant les deux points de vue.

Mettre à jour I

Des commentaires réfléchis (ci-dessous) de Travis Service et Alex ten Brink suggèrent (en effet) qu'au T1, l'expression "indécidable" n'est pas synonyme de "non vérifiable" et que les réponses au T2-5 peuvent dépendre de cette distinction. Il n'est pas du tout clair (pour moi) quel choix de définition conduirait aux théorèmes les plus forts, et aussi, capturer le mieux notre intuition de la classe P. Les réponses et commentaires qui répondent à cette question sont les bienvenus.

Une remarque de Felix Klein dans ses mathématiques élémentaires d'un point de vue avancé: la géométrie (1939) me vient à l'esprit:

Un autre exemple de concept qui se produit avec plus ou moins de précision dans la perception naïve de l'espace, que nous devons ajouter en complément de notre système de géométrie, est la notion de courbe (arbitraire) . Chaque personne croit savoir ce qu'est une courbe jusqu'à ce qu'elle ait appris tellement de mathématiques que les innombrables anomalies possibles les confondent.

Comme avec les courbes, donc avec les langages acceptés par les machines Turing en  ... ce qui me semblait (comme) le plus simple et le plus naturel de toutes les classes de complexité me confond maintenant par les (innombrables?) Attributs invérifiables et / ou indécidables de ses membres . La motivation générale en demandant Q1–5 était de trouver un chemin à travers ce fourré déroutant, mais les réponses données jusqu'à présent (par Travis Service et Alex ten Brink) ont fourni d'autres motifs de confusion!$P$

La génération de mathématiciens de Klein a travaillé d'arrache-pied pour trouver de bonnes définitions des courbes et d'autres éléments fondamentaux de la théorie, de la géométrie et de l'analyse des ensembles. Un aperçu au niveau élémentaire peut être trouvé dans la discussion Wikipedia de la sphère cornue d'Alexandre

      
      Une intégration d'une sphère dans R3

Au cours du 20e siècle, l'analyse des «variétés sauvages» comme la sphère d'Alexander a aidé à clarifier les distinctions entre les variétés topologiques, les variétés continues par morceaux et les variétés différentielles. De même au 21e siècle, peut-être que des raffinements des définitions associées à aideront à apprivoiser les langages sauvages de P et les machines de Turing sauvages… bien que spécifier des raffinements appropriés ne sera pas une tâche facile.$P$$P$

Contexte

Ces questions liées découlent des questions wiki de la communauté MathOverflow " Quels sont les problèmes indécidables de Turing les plus attractifs en mathématiques? " Et " Quelles notions sont utilisées mais pas clairement définies dans les mathématiques modernes? " En particulier, Colin Tan a demandé que la question posée ci-dessus soit affiché comme une question distincte.

Pour le contexte technique, voir la question TCS StackExchange " Les limites d'exécution en P sont-elles décidables? ", En particulier la preuve concise d'Emanuele Viola que la réponse est "non". Notez également que des résultats similaires sont prouvés par Juris Hartmanis dans sa monographie Calculs faisables et propriétés de complexité prouvables (1978).

Cette semaine, le blog Lance Fortnow / Bill GASARCH, Complexity Computational, organise son sondage décennal " Does or Not?$P=NP$ " - la cinquième et dernière question posée invite à commenter la question Fortnow / GASARCH.

Pour la question 1, la réponse est non. Soit un langage dans P et soit M tout temps polynomial Machine de Turing reconnaissant L (dont le temps d'exécution est supposé indécidable). Pour chaque k ∈ N, soit M k soit la machine de Turing qui, à l'entrée x de longueur n, boucle d'abord pour n k étapes puis exécute M sur x pour n k + k étapes et accepte si M accepte x (dans ces n k + $L$$P$$M$$L$$k \in \mathbb{N}$$M_k$$x$$n$$n^k$$M$$x$$n^k + k$$M$$x$$n^k + k$étapes) et rejette le contraire. Le temps d'exécution de est Θ ( n k ) pour chaque k .$M_k$$\Theta(n^k)$$k$

Puisque s'exécute en temps polynomial, il existe un certain k ′ ∈ N tel que M s'exécute dans O ( n k ′ ) (même si nous ne savons pas ce que k ′ est) et donc pour tout k assez grand M k reconnaît L et a un runtime décidable.$M$$k' \in \mathbb{N}$$M$$O(n^{k'})$$k'$$k$$M_k$$L$

ÉDITER

Je pense que la réponse suivante est plus dans l'esprit de ce que l'affiche originale avait prévu avec la question 1.

Théorème: Il existe un langage tel que si N est une machine de Turing qui décide de L alors au moins une des conditions suivantes est vraie:$L \in P$$N$$L$

1) Il n'existe pas de preuve que accepte L , ou$N$$L$

2) Il n'existe pas de preuve que s'arrête dans les étapes f ( n ) (pour toute fonction f ( n ) ).$N$$f(n)$$f(n)$

Croquis de preuve: Soit une machine de Turing qui ne s'arrête pas sur la bande vierge et pour laquelle il n'existe pas de preuve que M ne s'arrête pas sur la bande vierge (les résultats de l'indépendance en informatique de Hartmanis et Hopcroft montrent qu'un tel M peut trouver efficacement).$M$$M$$M$

Soit .$L = \{ n : \exists n' \geq n \mbox{ s.t. } M \mbox{ halts in } n' \mbox{ steps when run blank tape}\}$

Puisque ne s'arrête pas, L est en fait le langage vide mais il n'y a aucune preuve de cela (car cela prouverait que M ne s'arrête pas).$M$$L$$M$

Soit n'importe quelle machine de Turing. S'il existe à la fois une preuve que N décide de L et une preuve que N s'exécute en étapes f ( n ), alors l'exécution de N lorsqu'il est exécuté sur l'entrée 1 fournit soit une preuve que M s'arrête (c'est-à-dire, si N accepte) ou que M fait pas s'arrêter (c.-à-d. si N rejette). Ainsi, si N décide prouvablement L alors N exécution de n'est pas décidable et vice versa.$N$$N$$L$$N$$f(n)$$N$$1$$M$$N$$M$$N$$N$$L$$N$

Oui, vous pouvez construire une machine qui prend du temps DTIME ( ) -DTIME ( n i ) où i est le nombre d'étapes prises par une machine Turing spécifique pour s'arrêter sur une bande vierge. Facile à construire et des constructions similaires valent pour à peu près n'importe quel aspect non trivial de P. Indique peu si P v NP est indécidable: Aucun problème pour prouver P ≠ EXP malgré les mêmes problèmes.$n^{i+1}$$n^i$$i$$\neq$

Après avoir réfléchi davantage sur le sujet, je pense avoir trouvé une réponse (possible) pour votre Q4 .

• Q4: Quels autres attributs de (outre les exposants d'exécution) sont actuellement connus pour être indécidables? Pour quels attributs de P cette question est-elle ouverte?$P$$P$

J'ai prouvé une variation sur le théorème de Rice qui répond à votre question pour la plupart des propriétés. Je vais essayer de m'expliquer plus clairement cette fois (la réponse de Travis Service était beaucoup plus claire et plus générale que ma réponse précédente).

Théorème: pour toute propriété détenant un ensemble non vide de langages infinis décidables (mais pas de langages finis), il est indécidable si une machine de Turing donnée décide d'un langage avec cette propriété, quand on lui promet que E s'arrête toujours en O ( f ( n ) ) temps, où f ( n ) = Ω ( n log n ) et f ( n ) = Ω ( g ( n ) ) , où g $E$$E$$O(f(n))$$f(n)=\Omega(n \log n)$$f(n)=\Omega(g(n))$$g(n)$ est le temps d'exécution pour une machine de Turing qui décide d'un langage avec cette propriété.

Rappelons qu'une Turing Machine (TM à partir de maintenant) décide d'une langue si elle accepte toutes les chaînes de la langue et rejette toutes les chaînes en dehors de la langue. Notez que nous pouvons prendre pour être autre chose qu'un polynôme, de sorte que le théorème est plus général qu'un simple P .$f(n)$$P$

Nous formalisons la notion de «propriété» comme un ensemble librement sélectionnable de langues «avec cette propriété». Décider si une langue a la propriété est alors équivalent à décider si la langue est membre de S . Tout comme dans le théorème de Rice, nous examinons si nous pouvons décider si la langue décidée par le TM d'entrée a la propriété spécifiée, et est donc en S . Notez que nous avons besoin de S ⊆ R , c'est-à-dire que S ne contient que des langages décidables.$S$$S$$S$$S \subseteq R$$S$

Veuillez noter que nous parlons des propriétés des langues , pas des MT. Votre question sur les exposants d'exécution n'est pas un cas particulier de ce théorème. Les propriétés de, disons, , pouvant être étudiées en prenant S ⊆ P , peuvent vous intéresser plus que les propriétés des MT fonctionnant en temps polynomial. Vous pouvez faire toutes sortes de choses cruelles à une MT, tout en conservant son exactitude et sa durée de fonctionnement, mais vous ne pouvez pas faire de même pour les langues.$P$$S \subseteq P$

L'exigence selon laquelle tous les langages en doivent être infinis est une technicité nécessaire pour la preuve, mais comme tous les langages finis sont décidables en temps constant et sont donc généralement sans intérêt, je ne pense pas que ce soit un problème majeur. Je m'attends à ce que la version généralisée qui permette également aux langues finies d'être vraies.$S$

Preuve du théorème . Supposons que l'on nous donne un TM avec un TM E comme paramètre, de sorte que P s'arrête toujours et accepte ssi E décide un langage en S , et où E est promis de toujours s'arrêter avec les temps d'exécution comme ci-dessus. Soit ( A , i ) une instance du problème d'arrêt, c'est-à-dire que A est une MT et i est une entrée pour A , et nous voulons maintenant décider si A s'arrête sur i .$P(E)$$E$$P$$E$$S$$E$$(A, i)$$A$$i$$A$$A$$i$

Étant donné que nous supposions est non vide, nous avons quelques s ∈ S . Puisque S ne contient que des langages décidables, il existe certains TM C décidant s . En particulier, nous choisissons le C avec le temps d'exécution g ( n ) comme supposé dans le théorème. Nous considérons maintenant la MT suivante:$S$$s \in S$$S$$C$$s$$C$$g(n)$

function H(x)
h := simulate A on i for |X| steps and return whether it halted
if h == 'halted' then
    reject
else
    if C(x) accepts then
        accept
    else
        reject
    fi
fi

On voit facilement que le temps de fonctionnement de cette MT répond aux exigences du théorème, car les TM peuvent être simulées en temps .$O(n \log n)$

Nous affirmons que ne renvoie aucun ssi A s'arrête sur i . Supposons que A s'arrête sur i après t étapes. H rejette donc tout X avec | X | ≥ t . Nous décidons donc tout au plus un langage fini, et donc H décide qu'aucun langage en S et P ( H ) ne retournera donc non .$P(H)$$A$$i$$A$$i$$t$$H$$X$$|X| \geq t$$H$$S$$P(H)$

Supposons maintenant que ne s'arrête pas sur i . Alors la variable halt n'aura jamais la valeur 'halted', donc nous décidons le même langage que C , qui est exactement s ∈ S , donc P ( H ) retournera vrai. Cela prouve que P ( H ) peut résoudre le problème d'arrêt, qui à son tour prouve le théorème.$A$$i$$C$$s \in S$$P(H)$$P(H)$

Je peux répondre à votre Q1 par la négative, répondant ainsi également aux Q2 et Q3 par la négative. Je ne suis pas sûr du Q4 ou Q5 cependant.

• Q1: Existe-t-il des langages reconnus uniquement par les machines Turing de P dont les exposants d'exécution sont indécidables ?$L$$P$

Il semble que vous ayez mal compris exactement ce qu'Emanuele Viola a prouvé dans sa brillante preuve que vous avez liée. Il a montré qu'il n'y a pas une seule machine Turing capable de calculer l'exposant d'exécution pour une machine Turing T présentée à M , même sous la promesse que T fonctionne en temps polynomial.$M$$T$$M$$T$

$T$$k$$T$$O(n^k)$$M$$k$$T$$T$$k$ $T$

$L$$P$, then there is some Turing Machine $T$ running in $O(n^k)$ for some $k$ that decides $L$, and hence there is the Turing Machine $M$ returning $k$ that decides the runtime exponent for $T$. This answers your question in the negative.

You might instead wonder about a different problem for a given language $L$ in $P$: given Turing Machine $T$ promised to run in polynomial time and promised to decide $L$, is it decidable to find the runtime exponent of $T$?

Unfortunately, this is also undecidable. Suppose we are given a language $L$ in $P$ and a TM (Turing Machine) $M$ capable of deciding for a given TM $T$ promised to run in polynomial time and promised to decide $L$, what the runtime exponent of $T$ is. We can prove this to be undecidable in a very similar way to what Emanuele Viola did: we use the exact TM he defined, and change it slightly: we now want this TM to decide $L$.

Since $L$ is in $P$, there is some TM deciding $L$ in $O(n^k)$ time. Our new TM $M$ first starts exactly as in Emanuele Viola's proof, running the (Halting Problem) TM for $n$ steps. It then loops either for $n^{k+1}$ steps or $n^{k+2}$ steps similarly to Emanuele Viola's TM. Finally, it solves $L$ on the given input and returns the answer.

$M$ is in $P$, decides $L$, and if we know the runtime exponent, we can decide the Halting Problem, so the above problem is also undecidable (for any language $L$). Note that we do not need to know $k$, we don't actually have to construct $M$, all we have to do is know it exists!

This kind of thinking about undecidability is quite common apparently, I remember a (blog?) post about a very similar issue: the question was "is it decidable whether Pi has a 'last zero'", so whether Pi stops having zeroes in its decimal representation if you go down far enough that representation. We currently don't know whether this is the case. We might not even be able to prove it, ever, or it might even be independent from our axiom systems (and thereby unprovable). But, since the answer is either true or false, a TM returning true and a TM returning false decide the issue either case and therefore the problem is decidable.

I'll see if I can find that post on the internet somewhere.

Edit:

I found it on Mathoverflow.