Peut-on déterminer si la langue L se situe dans NP?

Étant donné un langage L défini par une machine de Turing qui le décide, est-il possible de déterminer algorithmiquement si L se situe dans NP?

Non. D'abord, selon le théorème de Rice, c'est une propriété des MT qui ne dépend que du langage qu'ils calculent, donc elle ne peut pas être calculable.

Mais, plus que cela, on sait que l'ensemble d'index de (c'est-à-dire l'ensemble de MT qui calculent les langues dans N P ) est Σ 0 3 -complet ( Σ 0 3 dans la hiérarchie arithmétique de calculabilité, pas le hiérarchie polynomiale).$NP$$NP$$\Sigma^0_3$$\Sigma^0_3$

Des questions comme celle-ci ont d'abord été étudiées par Hajek . Pour plus d'informations, voir par exemple cet article de Ken Regan.

Quelques pépites de plus dans le papier de Hajek:

• L'ensemble d'index de est Σ 0 3 -complet.$P$$\Sigma^0_3$
• est Π 0 2 -complet$\{i : P^{L(M_i)} \neq NP^{L(M_i)}\}$$\Pi^0_2$
• Il y a une machine de Turing totale (s'arrête sur toutes les entrées) telle que P L i = N P L i mais la déclaration " P L i = N P L i " est indépendante (où L i = L ( M i ) ) . De même , pour relativisations où P ≠ N P .$M_i$$P^{L_i} = NP^{L_i}$$P^{L_i} = NP^{L_i}$$L_i = L(M_i)$$P \neq NP$

La réponse à votre question littérale est non, comme l'a souligné Joshua Grochow.

Cependant, comme Holger l'a indiqué, il est possible de vérifier en temps linéaire si la machine de Turing non déterministe (NTM) "s'horloge" et s'arrête après n ^ k pas pour une constante k, par une méthode standard de simulation d'une horloge (telle que la code ci-dessous). Souvent, lorsqu'un papier ou un livre suggère (à tort) qu'il est possible de déterminer si une MNT est du temps polynomial, c'est ce qu'ils signifient vraiment. C'est peut-être pour cela que vous avez posé la question? (J'avais la même question lorsque j'ai appris la théorie de la complexité pour la première fois et j'ai vu quelque part la déclaration selon laquelle il est possible de vérifier si une MT est polytemporelle.) La vraie question est de savoir pourquoi on peut souhaiter faire cela, que j'examinerai ci-dessous après avoir expliqué comment .

Il existe de nombreuses façons d'ajouter une telle fonction d'horloge. Par exemple, imaginez sur l'entrée x de longueur n, en exécutant alternativement une instruction de "l'algorithme principal" cadencé, puis une instruction de l'algorithme suivant, qui se termine par (quelque chose de proche) n ^ k étapes:

pour i_1 = 1 à n
  pour i_2 = 1 à n
...
        pour i_k = 1 à n
          pas d'opération;
revenir;

Si le code ci-dessus revient avant que l'algorithme principal ne s'arrête, arrêtez le calcul entier (par exemple, avec rejet).

L'algorithme qui décide si un NTM est de cette forme, s'il est interprété comme une tentative d'un algorithme pour décider si son entrée est un NTM poly-temps, signalera quelques faux négatifs: certains NTM sont garantis pour s'arrêter en temps polynomial, même si ils n'alternent pas l'exécution d'une instruction d'un algorithme avec une instruction d'une horloge comme le code ci-dessus (serait donc rejetée malgré le poly-temps).

Mais il n'y a pas de faux positifs. Si un NTM réussit le test, il s'arrête définitivement dans le temps polynomial, il définit donc un langage NP. Cependant, le comportement de son algorithme principal sous-jacent est peut-être modifié si l'horloge s'épuise parfois avant que l'algorithme principal ne s'arrête, ce qui entraîne le rejet du calcul même si l'algorithme principal peut avoir accepté s'il a eu suffisamment de temps pour terminer. Par conséquent, le langage choisi peut être différent de celui de l'algorithme principal. Mais, et ceci est essentiel, si l'algorithme principal en cours d'exécution est en fait un algorithme polynomial fonctionnant au temps p (n), et si la constante k dans l'horloge est suffisamment grande pour que n ^ k> p (n), alors l'algorithme principal s'arrête toujours avant la fin de l'horloge. Dans ce cas, la réponse de l'algorithme primaire n'est pas modifiée, donc l'algorithme primaire et le NTM cadencé le simulant décident donc du même langage NP.

Pourquoi est-ce important? Cela signifie qu'il est possible "d'énumérer tous les langages NP" (qui, comme je l'ai dit, est souvent inexact dans la littérature, comme "décider si un MNT donné est poly-temps" ou "énumérer tous les NTM poly-temps"). Plus précisément, il est possible d'énumérer une liste infinie de M_1 M_2, ... de NTM, avec les propriétés

1. Chaque M_k s'exécute en temps polynomial (par exemple, en attachant une horloge ^ k à M_k), décide donc un langage NP, et
2. Chaque langue NP est la langue décidée par certains M_i dans la liste.

Ce qui ne se produit pas, c'est que chaque NTM à temps polynomial figure sur la liste. Mais chaque langage NP a un nombre infini de NTM qui le représentent. Ainsi, chaque langage NP est garanti d'avoir au moins certains de ses NTM représentatifs sur la liste, spécifiquement tous ces NTM à un indice k suffisamment grand pour que n ^ k dépasse le temps d'exécution de M_k.

Ceci est utile pour faire des tours comme la diagonalisation, qui nécessitent d'énumérer par algorithme de telles listes infinies (ou illimitées) de tous les langages NP. Et bien sûr, toute cette discussion s'applique à de nombreux autres types de machines en plus des NTM poly-temps, tels que les TM déterministes poly-temps.

$p(n)$