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

10

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?

mba
la source
1
C'est peu probable. Peut être dur pour PPAD.
RB
Je ne sais pas si c'est une coïncidence ou non, mais cet article de blog a été publié aujourd'hui: ... un rappel que les problèmes de recherche totaux ne sont pas complets .
Pål GD

Réponses:

6

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 .

Rahul Savani
la source
2

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.PP(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.

Juho
la source
1

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. RMSATRM

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ésoutM
R
MMM
R
MM
RMSAT.
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. SATcoNP
SATNPNPcoNP
coNPNPNP=coNP



NP=coNP


la source
1
Je ne comprends rien de tout ça. Pouvez-vous définir une "réduction de Turing co-non déterministe à temps polynomial uniquement", un "anti-certificat", et clarifier également ce qu'est (la "réduction de R SAT" n'a aucun sens pour moi)? M
Sasho Nikolov
Une "réduction de Turing co-non déterministe à temps polynomial uniquement oui-réponse" est une machine à oracle coNP dont l'oracle est à quoi sert la réduction, de telle sorte qu'elle ne questionnera jamais l'oracle sur une entrée pour laquelle il n'y a pas de taille polynomiale string que la requête est liée par . (suite ...)R
(... suite) Un anti-certificat est l'analogue d'un certificat , avec OUI et NON échangés. est la réduction mentionnée dans la phrase qui a introduit . (J'ai corrigé la faute de frappe à la fin de cette phrase.) MM
1

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 .Tpx,1ny{0,1}p(n)T(x,y,1n)yx

Une question pourrait alors être de savoir si un algorithme de temps polynomial pour «COMPUTE Y» impliqueP=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.AA(ϕ)=1ϕA(ϕ)=0A¯A¯(ϕ)=0ϕA¯(ϕ)=1ϕ

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=coNPA¯yTNP=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 PNP=coNPNPkNP

Joe Bebel
la source