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

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 ) $k$$M$$M$ ${O}(n^k)$$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.

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 $(M,x)$$M'$$n$$M$$x$$n$$M$$n^2$$n^3$

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 $M$$x$$t=O(1)$$M'$$O(n^2)$$M$$M'$$n^3$

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$M$$x$$M'$$O(n^2)$$O(n^3)$

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.$P$$H$

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)\downarrow$$M$$x$$M^*$

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:

$\begin{align*} M(x) \downarrow \quad &\Rightarrow \exists n_0 \in \mathbb{N} : M \text{ halts on } x \text{ after at most } n_0 \text{ steps} \\ &\Rightarrow \forall y : n \geq n_0 \Rightarrow M^*(y) \text{ executes } n^2 \text{ arbitrary steps} \\ &\Rightarrow T_{M^*}(n) \in \mathcal{O}(n^2) \end{align*}$

et

$\begin{align*} M(x) \uparrow \quad &\Rightarrow \forall n \in \mathbb{N} : M \text{ does not halt on } x \text{ in less than } n \text{ steps} \\ &\Rightarrow \forall y : M^*(y) \text{ executes } n^3 \text{ arbitrary steps} \\ &\Rightarrow T_{M^*}(n) \in \Omega(n^3) \end{align*}$

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) \Leftrightarrow P(M^*,2)$$P$$H$$\square$

Du côté positif, il est décidable de savoir si une machine Turing à bande unique fonctionne dans le temps pour , voir:$n \mapsto C \cdot n + D$$C, D \in \mathbb{N}$

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

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).

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. $Σ^0_2$

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 .$Σ^0_2$$S$$S$$O(n^2)$$Σ^0_2$$S$

Pour le prouver, choisir un complète , avec temps polynomial (pour les nombres binaires).$Σ^0_2$$φ$$φ(x) ⇔ ∃k ∀m \, ψ(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(n^2)$$n$

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

$n^2$

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 $c$$≤n^2+c$$Π^0_1$$Σ^0_2$

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.

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. □