Trouver un témoin peut-il être difficile à NP même si nous savons déjà qu'il y en a un?

Les exemples courants de problèmes NP-difficiles (clique, 3-SAT, vertex cover, etc.) sont du type où nous ne savons pas si la réponse est "oui" ou "non" au préalable.

Supposons que nous ayons un problème dans lequel nous savons que la réponse est oui, en outre, nous pouvons vérifier un témoin en temps polynomial.

Peut-on alors toujours trouver un témoin en temps polynomial? Ou ce «problème de recherche» peut-il être difficile à NP?

TFNP est la classe des fonctions à valeurs multiples avec des valeurs qui sont vérifiées polynomialement et dont l'existence est garantie.

Il existe un problème dans TFNP qui est FNP-complet si et seulement si NP = co-NP, voir le théorème 2.1 dans:

Nimrod Megiddo et Christos H. Papadimitriou. 1991. Sur les fonctions totales, les théorèmes d'existence et la complexité de calcul. Théor. Comput. Sci. 81, 2 (avril 1991), 317-324. DOI: 10.1016 / 0304-3975 (91) 90200-L

et les références [6] et [11] à l'intérieur. PDF disponible ici .

Non, vous ne pouvez pas toujours trouver une solution en temps polynomial, même si vous savez qu'il existe une solution.

Selon Khanna, Linial et Safra [1] (voir le 3ème paragraphe), il résulte déjà du travail classique de Karp en 1972 que la coloration d'un graphique à 3 couleurs avec 3 couleurs est NP-difficile. (Leur travail étend cela pour montrer que les graphiques à 4 couleurs et 3 couleurs sont toujours NP-difficiles).

Notez que cela ne contredit pas la réponse de Rahul Savani . En effet, pour toutes les relations binaires dans FNP, il faut pouvoir vérifier en temps polynomial si est dans la relation. Étant donné que décider si un graphique à 3 couleurs avec 3 couleurs est NP-complet, il est peu probable que le problème de trouver une couleur à 4 couleurs dans un graphique à 3 couleurs se trouve dans FNP car nous ne pouvons pas vérifier la validité de l'entrée en temps polynomial . Il n'y a donc pas de contradiction avec le résultat Megiddo-Papadimitriou.$P$$P(x,y)$$x$

[1] Khanna, Sanjeev, Nathan Linial et Shmuel Safra. "Sur la dureté de l'approximation du nombre chromatique." Theory and Computing Systems, 1993., Actes du 2e Symposium israélien sur le. IEEE, 1993.

Si une relation NP est NP-difficile par rapport aux
réductions de Turing co-non déterministes à temps de polynôme non-déterministe, alors. Preuve: si une relation NP est NP-difficile par rapport aux réductions de Turing co-non déterministes à temps de polynôme non déterministe, alors:$\: NP = coNP \;$

Que soit une telle relation dure, et que soit un oui-réponse seule co-temps nondéterministe polynomiale de réduction de Turing à . Soit l'algorithme coNP donné par: Essayez d'analyser le prétendu anti- certificat en un certificat interne et des réponses. Si cela échoue, affichez OUI, sinon essayez d'exécuter sur l'anti-certificat interne en donnant la même réponse que celle donnée précédemment pour les requêtes répétées et en utilisant les réponses de l'anti-certificat (externe) pour toutes les autres requêtes oracle. $R$$M'$$SAT$$R$$\:$$M$
$\;$
$\;$$M'$
$\;$
$\;$$\:$Si rendrait plus distinct requêtes que le nombre de réponses ou l'une de ses requêtes ne serait pas lié par à la réponse de cette requête ou produirait OUI, les sorties OUI, sinon sorties NON. Étant donné que le fait d'être un oracle pour impose simplement des conditions indépendantes sur les réponses de l'oracle et que est une réduction oui-réponse uniquement, les paires requête-réponse produites par et un anti-certificat valide peuvent toujours être étendues à un oracle pour , donc résout$M'$
$\;$$R$
$\;$$M'$$M$$M$
$R$
$M'$$M'$
$R$$M$$SAT\hspace{-0.02 in}$.
Ainsi. Puisque est dur par rapport aux réductions déterministes du temps polynomial,. Par symétrie,. Ainsi. Par conséquent, si une relation NP est NP-difficile par rapport aux réductions de Turing co-non déterministes à temps polynomial uniquement , alors. $\: SAT\in coNP \;$
$SAT$$NP$$\: NP\subseteq coNP \;$
$\: coNP \subseteq NP \;$$\;\;\;\;$$\: NP = coNP \;$



$\: NP = coNP \;$

Cela dépend un peu de l'interprétation précise de votre question, mais je pense que votre scénario peut être génériquement décrit comme un problème « COMPUTE Y » où donné un algorithme de temps polynomial fixe universel et polynôme , sur l' entrée , affichez une chaîne , de telle sorte que génère 1, et existe toujours pour tous les possibles .$T$$p$$\langle x, 1^n \rangle$$y \in \{0,1\}^{p(n)}$$T(x,y,1^n)$$y$$x$

Une question pourrait alors être de savoir si un algorithme de temps polynomial pour «COMPUTE Y» implique$P = NP$

Dans ce cas, supposez que vous pouvez résoudre (disons) 3SAT en temps polynomial avec un nombre constant d'appels à un oracle qui résout 'COMPUTE Y', c'est-à-dire un algorithme où ssi est satisfaisable, sinon. Retournez le bit de sortie pour obtenir , un algorithme où si est satisfaisable et si n'est pas satisfaisant.$A$$A(\phi) = 1$$\phi$$A(\phi)=0$$\bar{A}$$\bar{A}(\phi) = 0$$\phi$$\bar{A}(\phi) = 1$$\phi$

Convertissez cet algorithme (qui utilise un oracle pour 'COMPUTE Y') en un algorithme non déterministe (qui n'utilise aucun oracle) en remplaçant simplement chaque appel oracle par une supposition non déterministe de que vous pouvez vérifier avec un appel à . Vous avez maintenant un algorithme non déterministe qui décide avec succès des instances 3CNF insatisfaisantes, donc yTNP=coN$\bar{A}$$y$$T$$NP = coNP$

Soit dit en passant , si , cela implique que tous problèmes complets (comme -clique ou 3SAT) ont de légères variations dont le problème de décision est facile (toujours «oui») mais dont la version de recherche est difficileN P k N $NP = coNP$$NP$$k$$NP$