Est-ce que «le deuxième X est NP-complet» signifie «X est NP-complet»?

Le problème du "deuxième " est le problème de décider de l'existence d'une autre solution différente d'une solution donnée par exemple. $X$

Pour certains problèmes -complets, la deuxième version de la solution est -complete (décidant de l'existence d'une autre solution pour le problème d'achèvement du carré latin partiel) tandis que pour d'autres, elle est soit triviale (Second NAE SAT), soit ne peut pas être complet (deuxième cycle hamiltonien dans les graphiques cubiques) sous une conjecture de complexité largement répandue. Je m'intéresse à la direction opposée. $NP$ $NP$ $NP$

Nous supposons un naturel problème où il est naturel vérificateur efficace qui vérifie un naturel intéressant relation où est une instance d'entrée et est un court témoignage de membres de dans . Tous les témoins ne peuvent être distingués du vérificateur. La validité des témoins doit être décidée en exécutant le vérificateur naturel et il n'a aucune connaissance d'un témoin correct (les deux exemples dans les commentaires sont des solutions par définition). $NP$ $X$ $(x, c)$ $x$ $c$ $x$ $X$

Est-ce que "Second est NP-complet" implique " est NP-complet" pour tous les problèmes "naturels" ? $X$ $X$ $X$

En d'autres termes, existe-t-il un problème "naturel" où cette implication échoue? $X$ . Ou équivalent,

Y a-t-il un problème "naturel" dans et non connu pour être complet mais son deuxième problème est complet? $X$ $NP$ $NP$ $X$ $NP$

EDIT : Grâce aux commentaires de Marzio, je ne suis pas intéressé par les contre-exemples artificiels. Je ne suis intéressé que par des contre-exemples naturels et intéressants pour des problèmes NP-complets similaires à ceux ci-dessus. Une réponse acceptable est soit une preuve de l'implication ci - dessus ou un contre-exemple « Deuxième problème X » qui est défini pour naturel, intéressant et bien connu problème . $X$ $NP$ $X$

EDIT 2 : Merci à la discussion fructueuse avec David Richerby, je l' ai modifié la question l' accent que mon intérêt est que des problèmes naturels . $X$

EDIT 3 : Motivation: Premièrement, l'existence d'une telle implication peut simplifier les preuves d'exhaustivité de nombreux problèmes Deuxièmement, l'existence de l'implication lie la complexité de décider de l'unicité de la solution au problème de décider de l'existence d'une solution pour les problèmes $NP$ $NP$ $NP$

cc.complexity-theory unique-solution Mohammad Al-Turkistany
la source

Les commentaires ne sont pas pour une discussion approfondie; cette conversation a été déplacée vers le chat .

Bjørn Kjos-Hanssen

Votre EDIT 3 et EDIT 1 ne semblent pas s'aligner. Si vous voulez que ce soit un résultat général, utile pour simplifier les preuves d'exhaustivité de NP, vous ne pouvez pas également dire que vous ne voulez que des contre-exemples "non artificiels". De plus, il serait utile d'avoir une définition de "naturel / intéressant", qui ne soit pas basée sur une opinion personnelle.

Chris Jefferson

Réponses:

Non,

Considérons le problème "Trouver un sous-ensemble d'un ensemble d'entiers S qui résume à 0".

Ce problème est trivial, car on peut retourner l'ensemble vide.

Cependant, trouver une deuxième solution après avoir renvoyé l'ensemble vide est le problème de somme de sous-ensemble bien connu, qui est connu pour être NP-complet.

Chris Jefferson
la source

À moins que vous ne puissiez définir un problème «contre nature», cela n'a pas d'importance. Les gens définissent des centaines de variantes de problèmes comme la somme de sous-ensembles et SAT.

Chris Jefferson

@Mohammad: Voici un autre contre-exemple; Je vous laisse le soin de décider s'il est naturel ou non: un jeu bimatrix a toujours au moins un équilibre de Nash et il est difficile pour NP de décider si un jeu bimatrix a plus d'un équilibre de Nash [Gilboa et Zemel, GEB 1989] . La construction prend une formule SAT f et produit un jeu avec un certain équilibre de Nash de forme connue qui existe toujours, de telle sorte que le jeu a un deuxième équilibre si la formule f n'est pas satisfaisante.

Rahul Savani

Voici un autre contre-exemple, la version unidimensionnelle du lemme de Sperner, qui est similaire dans l'esprit à celui que Rahul fournit. Étant donné un circuit booléen calculant une fonction

(l'entrée est fournie en binaire) avec la promesse que

, trouver un nombre

f : {0, 1, 2, \dots, 2^{n} - 1} \to {0, 1}

$f : \{0,1,2,\ldots,2^n-1\} \to \{0,1\}$

f (0) = 0

$f(0) = 0$

f (2^{n} - 1) = 1

$f(2^n-1)=1$

k

$k$ tel que

. Un tel nombre existe toujours et est facile à trouver via la recherche binaire, mais il est difficile pour NP de décider s'il existe plusieurs positions de ce type.

f (k) = 0

$f(k) = 0$

f (k + 1) = 1

$f(k+1) = 1$

Robert Andrews

NP complete ne signifie pas que toutes les instances sont difficiles, juste quelques-unes. Il existe de nombreuses instances triviales de sous-ensemble (tous les problèmes qui contiennent 1 et - 1 par exemple) et de nombreux problèmes SAT faciles (2 SAT par exemple), mais SAT dans son ensemble est toujours NP-complet.

Chris Jefferson

La réponse doit être un sous-ensemble de l'ensemble des entiers S. {} est un sous-ensemble de S car l'ensemble vide est un sous-ensemble de tous les ensembles. {ϕ} n'est pas un sous-ensemble de S, car S ne contient pas ϕ

Chris Jefferson

La réponse est oui (si la réduction ASP est utilisée à la place de la réduction Karp). La réduction ASP requiert une bijection polynomiale calculable en temps entre les ensembles de solutions des deux problèmes. Cela permet une réduction parcimonieuse entre les problèmes ASP complets. Yato et Seta déclarent que la complétude implique la complétude (page 2, deuxième paragraphe). Un autre problème de solution (ASP) est exactement ce que j'appelle le problème Second X. $ASP$ $NP$

Oded Goldreich déclare que "toutes les réductions connues parmi les problèmes naturels de complétés sont soit parcimonieuses, soit facilement modifiables". ( Complexité informatique: une perspective conceptuelle par Oded Goldreich ). Par conséquent, il est plausible que les réductions de Karp entre les problèmes naturels NP-complets puissent être modifiées pour être des réductions ASP. $NP$

Mohammad Al-Turkistany
la source

Votre problème était de savoir si la complétude NP de la deuxième solution implique la complétude NP. Ce qu'ils montrent est plus faible, ils nécessitent une complétude ASP, car la complétude NP n'est pas suffisante, comme indiqué dans les commentaires à votre question.

domotorp

Si quelqu'un lit cela, cette réponse est fausse. Il est facile de produire un problème où Second X est NP-complet, mais X n'est pas NP-complet. Par exemple (comme discuté dans les commentaires ci-dessus), le problème de trouver un sous-ensemble d'un ensemble d'entiers qui résume à 0 est Second X NP-complete, car il est NP-complete une fois que nous rejetons la première solution facile de l'ensemble vide .

Chris Jefferson

Cette réponse n'a pas de sens pour moi. L'article montre que la complétude ASP d'un problème

implique que le problème de la deuxième solution

pour

est NP-complet. Mohammad fait valoir que les problèmes naturels NP-complets devraient être ASP complets. Cela signifierait donc que pour les problèmes naturels NP-complets

, le problème

est NP-complet. Mais la question initiale demande l'inverse: elle demande si la dureté de

implique la dureté de

. Donc, je suis presque sûr que cette réponse a fait reculer la logique. Ai-je oublié quelque chose?

Π

$\Pi$

Π_{[2]}

$\Pi_{[2]}$

Π

$\Pi$

Π

$\Pi$

Π_{[2]}

$\Pi_{[2]}$

Π_{[2]}

$\Pi_{[2]}$

Π

$\Pi$

Sasho Nikolov

Il est un peu étrange pour quelqu'un de poser une question, d'y répondre et de l'accepter pendant la discussion.

Chandra Chekuri

@ MohammadAl-Turkistany Mon commentaire disait que votre réponse semble avoir fait reculer la logique et ne répond pas à votre propre question. Je n'ai rien dit sur l'exemple de Chris (ce qui me semble bien, mais je ne veux pas entrer dans cet argument dans les commentaires).

Sasho Nikolov