Quelle est la différence entre «décision» et «vérification» dans la théorie de la complexité?

Dans la théorie de calcul de Michael Sipser à la page 270, il écrit:

P = la classe de langues dont l'adhésion peut être décidée rapidement.
NP = la classe de langues dont l'appartenance peut être vérifiée rapidement.

Quelle est la différence entre «décidé» et «vérifié»?

La tâche de décider de l' appartenance est: pour toute entrée , décider si x ∈ L , c'est-à-dire calculer la fonction suivante:$x$$x \in L$

$\qquad \displaystyle \chi_L(x) = \begin{cases}1 &x \in L \\ 0 & x\notin L\end{cases}$

D'un autre côté, la tâche de vérification de l' appartenance est la suivante: étant donné toute entrée et une preuve (ou témoin ) d'adhésion (proposée) , vérifiez rapidement si x ∈ L par cette preuve ¹.$x$$x\in L$

Par exemple, considérons la factorisation principale. Étant donné , calculez tous les facteurs premiers de n . En revanche, étant donné ( n , { i 1 , … , i k } ) , vérifier que ∏ k j = 1 i j = n . Quel est le plus simple?$n \in \mathbb{N}$$n$$(n, \{i_1, \dots, i_k\})$$\prod_{j=1}^k i_j = n$

Autre exemple: étant donné un graphique pondéré , décidez s'il existe un cercle de Hamilton (qui visite tous les nœuds) avec un poids au plus k . D'autre part, étant donné ( G , ( v 1 , … , v n ) ) , vérifier si le chemin v 1 → ⋯ → v n visite tous les nœuds exactement une fois et a un poids au plus k . Quel est le plus difficile?$G = (V,E)$$k$$(G, (v_1, \dots, v_n))$$v_1 \to \dots \to v_n$$k$

1. Vous direz donc "non" si mais la preuve est fausse. C'est bien, cependant, car nous considérons les machines non déterministes dans ce contexte; il est seulement important que nous puissions deviner la bonne preuve et la vérifier (rapidement).$x \in L$

Si nous ignorons les problèmes d'efficacité, il existe un autre exemple qui illustre la différence par analogie. Nous savons que le problème d'arrêt n'est pas décidable: étant donné un code pour une machine de Turing, il n'existe aucun moyen efficace de déterminer si la machine s'arrête si elle est exécutée sans entrée.$e$

Mais si une machine ne arrête, il est difficile de prouver à quelqu'un d' autre: il suffit de leur dire combien de pas la machine fonctionne avant d'arrêter. Ils peuvent exécuter la machine pour autant d'étapes et savoir si vous avez dit la vérité (en ignorant l'efficacité, bien sûr).

L'ensemble des machines Turing à l'arrêt n'est donc pas décidable, mais il est vérifiable. Notez qu'aucune preuve ne doit être donnée pour les machines qui ne s'arrêtent pas . La vérification est asymétrique en ce sens que seule l'appartenance à l'ensemble peut être vérifiée, l'appartenance à l'ensemble non.

La situation avec P et NP est analogue. Une langue est en NP s'il existe un système de preuves tel que chaque objet qui est dans la langue a une courte preuve (délimitée par un polynôme de la taille de l'objet) qui peut être vérifiée efficacement (avec un certain nombre d'étapes délimitées par un polynôme dans la taille de l'entrée).

D'un autre côté, un langage est en P s'il existe un moyen de dire si un objet arbitraire est ou non dans le langage en utilisant un certain nombre d'étapes délimitées par un polynôme dans la taille de l'objet. Maintenant, nous devons nous soucier des entrées arbitraires, pas seulement des objets dans le langage. Mais ce problème est symétrique: si un langage est en P alors son complément l'est aussi. La question de savoir si le complément de chaque langue NP est également une langue NP n'est pas résolue.

(Cette analogie pourrait suggérer que les problèmes NP sont liés à des problèmes P comme les ensembles sont des ensembles calculables. C'est quelque peu vrai, mais cela peut être trompeur. C'est un fait fondamental qu'un ensemble qui est re et co-re est calculable, tandis que on ne sait pas si chaque ensemble qui est NP et Co-NP est en P).