Dureté d'approximation en supposant NP! = CoNP

32

Deux des hypothèses courantes pour prouver la dureté des résultats d'approximation sont et Conjecture de jeux uniques. Existe-t-il une dureté des résultats d'approximation en supposant que N P c o N P ? Je recherche le problème A tel qu'il "est difficile d'approximer A à l' intérieur d'un facteur α à moins que N P = c o N P ".PNPNPcoNPAAαNP=coNP

On sait que "montrer le facteur NP-dureté pour le problème de vecteur le plus court impliquerait que N P = c o N P ". Notez que c'est "l'opposé" de ce que je recherche.nNP=coNP

Clarification: Il est possible que et la question P vs NP soit toujours ouverte. Je suis à la recherche de la dureté du résultat d'approximation qui deviendra false si N P = c o N P mais n'est pas affecté (c. -à- reste encore comme une conjecture) par P N P .NP=coNPNP=coNPPNP

Shiva Kintali
la source
@ Kintali, Le résultat SVP est intéressant. Connaissez-vous d'autres exemples similaires au résultat du problème de vecteur le plus court?
Mohammad Al-Turkistany
Je ne connais pas plus de tels résultats.
Shiva Kintali

Réponses:

20

Voici une observation simple. Si vous supposez , alors il est assez facile de voir qu'il existe des problèmes d'optimisation N P qui n'ont même pas de bons algorithmes d'approximation non déterministes , dans un certain sens.NPcoNPNP

Par exemple, le théorème du PCP dit que vous pouvez traduire SAT dans le problème de distinguer si des clauses sont satisfaites et toutes les clauses sont satisfaites, pour certains ε > 0 . Supposons qu'il existe un algorithme non déterministe qui puisse faire la distinction entre ces deux cas, en ce sens que l'algorithme non déterministe peut signaler dans chaque chemin de calcul "tous satisfaits" ou "au plus 1 - ε ", et il dit "au plus 1 - ε" "dans un chemin si au plus 1 - ε1εε>01ε1ε1εpeut être satisfaite, sinon il dit "tout satisfait" dans chaque chemin de calcul si toutes les équations peuvent être satisfaites. Cela suffit pour décider SAT , alors N P = c o N P . Il semble clair que l'existence d'un tel algorithme non déterministe n'a pas d' incidence si P = N P .coNPNP=coNPP=NP

Il est tout à fait plausible qu'un scénario plus « naturel » existe: un problème d'optimisation qui est difficile à approximative en déterministe polynomial sous mais pas connu pour être dur sous P N P . (C'est probablement ce que vous vouliez vraiment demander.) De nombreux résultats de dureté d'approximation sont d'abord prouvés sous une hypothèse plus forte (par exemple N P pas en temps sous-exponentiel, ou N P pas en B P P ). Dans certains cas, des améliorations ultérieures affaiblissent l'hypothèse nécessaire, parfois jusqu'à P NNPcoNPPNPNPNPBPP . Il y a donc de l'espoir qu'il y ait une réponse un peu plus satisfaisante à votre question que celle-ci. Il est difficile dedemander comment il pourrait y avoir un problème quine peutêtre prouvé difficile derapprocher dans polynomial déterministe sous P N P , mais ilpeutêtre prouvé dur sous N P de la c o N P . Cela signifierait que N P c o N P nous dit quelque chose sur les calculs déterministes que P N P ne dit pas déjà; intuitivement, c'est difficile à saisir.PNPPNPNPcoNPNPcoNPPNP

Ryan Williams
la source
Oui. Il est difficile de comprendre que de tels résultats de dureté sont même possibles. Je me demandais si nous pouvions prouver l'inexistence de tels résultats de dureté. Ouf .... ça devient compliqué.
Shiva Kintali
(1) Je crains que vous n'écriviez le oui et le non dans le deuxième paragraphe. Il est facile de construire un algorithme non déterministe qui fait ce que vous avez dit (rapporte «tous satisfaits» dans au moins un chemin si la formule est satisfaisable et rapporte «au plus 1 − ε» dans tous les chemins si la formule est ε-loin d'être satisfaisable ) en testant simplement toutes les affectations de vérité de façon non déterministe. (2) Je suis d'accord sur la partie «difficile à saisir».
Tsuyoshi Ito
8

Avertissement: ce n'est pas une réponse directe.

En fait, il existe beaucoup plus de conditions de dureté que P! = NP et l'UGC. David Johnson a écrit une belle chronique pour les transactions sur les algorithmes en 2006 sur précisément cette question. Il énumère les nombreuses hypothèses différentes qui sont utilisées pour montrer la dureté et comment elles se rapportent les unes aux autres.

Malheureusement, ce sont toutes des classes NP vs déterministes (à l'exception de NP et co-AM). NP vs co-NP n'est pas du tout couvert.

Suresh Venkat
la source
2
En passant, David Johnson parle de NP vs co-NP dans la colonne suivante - la colonne 26 de complétude NP !
Daniel Apon
ah bien sûr. J'aurais dû m'en souvenir. Mais aucune approximation cependant ...
Suresh Venkat
4

NPcoNPPNPNPcoNPPNPPNPNPcoNP

Mohammad Al-Turkistany
la source
3
Il est possible que NP = coNP et toujours la question P vs NP soit ouverte. Je recherche la dureté du résultat d'approximation qui deviendra fausse si NP = coNP mais qui n'est pas affectée (c'est-à-dire qui reste toujours une conjecture) par P! = NP.
Shiva Kintali
AαNPcoNPα