Chaque problème NP-hard est-il calculable?

Faut-il qu'un problème NP-hard soit calculable?

Je ne pense pas, mais je ne suis pas sûr.

Non, un problème -hard n'a pas besoin d'être calculable. La définition est assez complète: un problème L est N P- difficile si ce problème ayant une solution poly-temps implique que chaque problème dans N P a une solution poly-temps (c'est-à-dire, une réduction à L existe pour chaque problème dans N P .).$NP$$L$$NP$$NP$$L$$NP$

Les problèmes non calculables sont alors vides de difficulté: supposons que nous puissions en résoudre un en temps polynomial. Ensuite, nous utilisons la preuve qu'il est non calculable pour déduire qu'il est à la fois calculable et non calculable, une contradiction. De ce mensonge, nous pouvons tirer n'importe quoi, à savoir qu'il existe un algorithme polynomial de temps pour tout problème nous examinons.$NP$

Par exemple, considérons le problème de l' arrêt . Nous pouvons réduire n'importe quel langage N P A à H comme suit, en supposant que nous avons un vérificateur de polytemps f ( s , c ) qui vérifie si c est un certificat pour s ∈ A :$H$$NP$$A$$H$$f(s,c)$$c$$s\in A$

• Étant donné l'entrée $s$
• Construct (mais ne pas courir) Machine de Turing qui prend entrée x tente chaque certificat c et arrête si c est un certificat attestant que l ∈ A .$M$$x$$c$$c$$s\in A$
• Retour (c'est-à-dire renvoie vrai si M s'arrête sur l'entrée x )$H(M,x)$$M$$x$

Ainsi, avec un seul appel à un algorithme poly-temps résolvant le problème d'arrêt, nous pouvons résoudre tout problème en temps polynomial.$NP$

Une telle réduction n'est pas utile, car elle ne fait que dire si "si faux alors quelque chose". Nous savons déjà qu'il n'y a pas d'algorithme de polytime pour les problèmes non calculables.

Il semble y avoir une grande confusion dans cette communauté concernant cette question. Je donnerai une réponse détaillée dans l'espoir d'éclaircir l'eau et d'éclairer la relation entre calculabilité et dureté NP.

Premièrement, je crois qu'être clair et explicite sur les différentes définitions impliquées résoudra une grande partie de la confusion.

UNE chaîne est une séquence finie de caractères d'un alphabet fini fixe.

UNE problème de décision est un ensemble de chaînes. (Cet ensemble est généralement infini.) Considérez le problème de décision comme testant des chaînes pour une propriété: les chaînes avec la propriété sont dans l'ensemble, et les chaînes sans la propriété ne le sont pas.

Supposons que nous avons deux problèmes de décision, et B . Disons que A est polynomial-temps réductible à B s'il y a un polynôme p ( x ) et un algorithme un algorithme M tel que, pour toutes les chaînes s ,$A$$B$$A$$B$$p(x)$$M$$s$

• Si vous fournissez à des entrées s , M s'arrête en moins de p ( | s | ) étapes (où | s | est la longueur de la chaîne s ) et génère une chaîne M ( s $M$$s$$M$$p(|s|)$$|s|$$s$$M(s)$ .
• est dans A si et seulement si M ( s ) est dans$s$$A$$M(s)$$B$ .

Un problème de décision est NP-difficile si, pour chaque problème de décision NP A , A est temps polynomial réductible à $B$$A$$A$$B$ .

Un problème de décision est calculable s'il existe un algorithme , qui, pour toutes les chaînes $M$$s$ ,

• Si vous fournissez à des entrées s , $M$$s$$M$ s'arrête et sort «oui» ou «non».
• La sortie est "oui" si est en A et "non" sinon.$s$$A$

Avec les définitions ci-dessus, nous pouvons immédiatement clarifier ce qui, à mon avis, pourrait être la racine de la confusion dans votre question: rien dans les définitions de problème de décision, de réduction ou de dureté NP n'exige que les problèmes de décision soient calculables. Les définitions ont un sens parfait en considérant les problèmes de décision comme des ensembles de chaînes arbitraires, et ces ensembles peuvent en effet être très méchants.

Cela laisse deux questions sur la table:

1. Les définitions laissent ouverte la possibilité que les fonctions non calculables puissent être NP-hard. Y at - il réellement non calculable, les fonctions NP-difficiles?
2. Il y a une intuition que dire qu'un problème est NP-difficile, c'est qu'il est difficile à résoudre. Dire qu'il n'est pas calculable, c'est comme dire qu'il est «vraiment difficile» à résoudre. Alors, tous les problèmes non calculables sont-ils difficiles à résoudre?

La question 1 est plus facile à répondre. Il existe deux façons particulièrement importantes de trouver des problèmes de décision non calculables qui sont difficiles à NP. Le premier est le problème de l' arrêt: le problème de l' arrêt, , a la propriété que chaque calculable problème de décision est réductible polynomial à H . Comme les problèmes NP sont calculables, chaque problème NP est polynomial-temps réductible à H , donc H est NP-difficile.$H$$H$$H$$H$

L'autre façon importante de construire un problème NP-dur non calculable est d'observer que nous pouvons combiner tout problème NP-dur connu avec n'importe quel problème non calculable connu. Soit NP-dur et B non calculable. Formez le problème de décision A ⊕ B comme suit: A ⊕ B contient les chaînes de la forme "0, suivie d'une chaîne en A " et celles de la forme "1, suivie d'une chaîne en B ". A ⊕ B est NP-difficile car nous pouvons transformer n'importe quelle réduction (de n'importe quel problème) en A en une réduction en A $A$$B$$A \oplus B$$A \oplus B$$A$$B$$A \oplus B$$A$$A \oplus B$: il suffit de modifier l'algorithme pour afficher un "0" supplémentaire à l'avant de sa chaîne de sortie. n'est pas calculable, car le calcul de A ⊕ B nécessite de décider quelles chaînes commençant par "1" sont dans l'ensemble; c'est impossible, car B n'est pas calculable.$A \oplus B$$A \oplus B$$B$

La question 2 est considérablement plus délicate, mais il existe en fait des problèmes de décision non calculables qui ne sont pas difficiles à NP (en supposant que P NP). La réponse fine de Yuval construit explicitement un tel problème de décision. (Pour tout théoricien de la calculabilité dans la pièce, tout "Cohen Π 0 $\neq$$\Pi^0_1$ -generic" fera aussi l'affaire.) Je vais expliquer pourquoi l'intuition selon laquelle "les problèmes NP-difficiles sont durs, les problèmes non calculables sont plus difficiles " est faux.

La dureté NP et la non-calculabilité indiquent toutes deux qu'un problème est "dur" dans un sens très général, mais elles sont très différentes et ne doivent pas être regroupées comme le même type de phénomène. Plus précisément, la dureté NP est une propriété "positive": un problème NP difficile est difficile dans le sens où, étant donné l'accès à une feuille de triche pour A , vous pouvez résoudre une classe difficile de problèmes$A$$A$ . En revanche, la non-calculabilité est une propriété "négative": un problème non calculable difficile dans le sens où vous ne pouvez pas résoudre A avec une classe de ressources donnée$A$$A$ .

("Forçage", soit dit en passant, est la technique utilisée pour produire le "Cohen générique" que j'ai mentionné. Pour être très très vague, le forçage est une façon générale de produire des choses qui sont "génériques" en ce sens aucune propriété positive et aucune propriété négative. C'est pourquoi le forçage peut produire directement un problème qui n'est ni calculable ni NP-difficile.)$\Pi^0_1$

Nan. NP-Hard signifie qu'il est aussi difficile, ou plus difficile, que les problèmes NP les plus difficiles. Intuitivement, être non calculable rendra la tâche beaucoup plus difficile que NP.

Wikipédia:

Il y a des problèmes de décision qui sont NP-dur mais pas NP-complet, par exemple le problème d'arrêt.

Tout le monde sait que ce n'est pas calculable

Pour être complet, prouvons le théorème suivant:

Il existe un langage non calculable qui n'est pas NP-dur si et seulement si P NP.$\neq$

Si P = NP alors n'importe quel langage non trivial (un qui diffère de $\emptyset,\{0,1\}^*$ ) est NP-dur (exercice), et en particulier tout langage non calculable est NP-dur.

Supposons maintenant que P NP. Soit T i une énumération de toutes les machines de Turing. Nous allons construire le langage L requis par étapes. A chaque étape , nous garderons un { 0 , 1 , ? } coloration de { 0 , 1 } ∗ que nous désignons également par L ; ici 0 signifie que nous avons décidé que la chaîne n'est pas en L , 1 signifie que nous avons décidé que la chaîne est en L , et $\neq$$T_i$$L$$\{0,1,?\}$$\{0,1\}^*$$L$$0$$L$$1$$L$$?$signifie que nous n'avons pas encore décidé. Tout sauf un nombre fini chaînes seront de couleur $?$.

À l'étape , nous considérons T i comme une machine qui accepte son entrée, la rejette ou ne s'arrête jamais. Si T i ne s'arrête pas toujours, nous ne faisons rien. Si T i s'arrête toujours alors on trouve une chaîne x telle que L ( x ) = ? , et définissez L ( x ) : = 0 si T i ( x ) accepte et L ( x ) : = 1 si $2i$$T_i$$T_i$$T_i$$x$$L(x) = ?$$L(x) := 0$$T_i(x)$$L(x) := 1$$T_i(x)$ rejette.

À l'étape , nous considérons T i comme une machine calculant une fonction (éventuellement) partielle sur son entrée. Si T i n'est pas total, ou s'il est total mais ne s'exécute pas en temps polynomial, ou s'il est total mais sa plage est finie, nous ne faisons rien. Si T i est total, s'exécute en temps polynomial et a une plage infinie, alors nous trouvons une chaîne x telle que L ( T i ( x ) ) = ? . Si x ∈ S A T (c'est-à-dire si $2i+1$$T_i$$T_i$$T_i$$x$$L(T_i(x)) = ?$$x \in \mathrm{SAT}$$x$code un CNF satisfaisable), puis nous définissons , et sinon nous définissons L ( x ) : = 1 .$L(x) := 0$$L(x) := 1$

Après de nombreuses étapes infiniment, nous obtenons un coloration de { 0 , 1 } ∗ que nous complétons à un langage réel de manière arbitraire.$\{0,1,?\}$$\{0,1\}^*$

Le langage résultant n'est pas calculable: l'étape 2 i garantit que T i ne le calcule pas. Ce n'est pas non plus difficile à NP, mais ici le raisonnement est un peu plus délicat. Supposons que T i est une réduction de la polynomial de SAT à L . Si la plage de T i est finie, alors nous pouvons transformer T i en une machine polytime décidant SAT, en listant la table de vérité de L sur la plage de T i . Ceci est impossible par l'hypothèse P ≠ NP. Ainsi T i a une plage infinie, mais alors l'étape 2 $L$$2i$$T_i$$T_i$$L$$T_i$$T_i$$L$$T_i$$\neq$$T_i$ exclut qu'il soit une réduction parà SAT L .$2i+1$$L$

Un langage est NP-difficile si pour chaque L ' ∈ N P nous avons que L ' est réductibles polynomial à L . Le problème d'acceptation des machines de Turing non déterministes$L$$L' \in \mathrm{NP}$$L'$$L$

est indécidable et est NP-difficile. Pour envisager une . L ' est décidé par une machine de Turing non déterministe M ' avec une complexité temporelle polynomiale. Une réduction poly-temps f de L ' en A N T M est donnée par$L' \in \mathrm{NP}$$L'$$M'$$f$$L'$$A_{\mathsf{NTM}}$

Je pense que ce qui pousse les gens à penser qu'il n'y a pas de problème NP-dur non calculable, c'est qu'ils manquent le point que la dureté NP est une limite inférieure de la dureté d'un problème, pas une limite supérieure de leur dureté comme P ou NP.

Un langage L étant NP-dur signifie qu'il est au-dessus du langage en NP et c'est. Maintenant, si vous comprenez cela, ce qu'il faut, c'est montrer qu'il y a un problème arbitraire plus difficile.

Soit une langue. Tenez compte des algorithmes avec une augmentée boîte noire qu'ils peuvent utiliser pour décider l' appartenance à un . Laissez-les noterons C A . Il est facile de voir que le problème d'arrêt pour C A , H a l t C A n'est pas dans C$A$$A$$\mathsf{C}^A$$\mathsf{C}^A$$Halt_{\mathsf{C}^A}$$\mathsf{C}^A$ .

$A$$A'$$A < A'$$A<A'<A''<A'''<...$