Dureté d'approximation en supposant NP! = CoNP

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 ".$P \neq NP$$NP \neq coNP$$A$$A$$\alpha$$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.$n$$NP = 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=coNP$$NP=coNP$$P \neq NP$

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.$NP \neq coNP$$NP$

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-\varepsilon$$\varepsilon > 0$$1-\varepsilon$$1-\varepsilon$$1-\varepsilon$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 .$coNP$$NP=coNP$$P = 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 ≠ $NP \neq coNP$$P \neq NP$$NP$$NP$$BPP$ . 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.$P \neq NP$$P \neq NP$$NP \neq coNP$$NP \neq coNP$$P \neq NP$

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.

$NP \ne coNP$$P \ne NP$$NP\ne coNP$$P\ne NP$$P\ne NP$$NP\ne coNP$

Ce n'est pas une réponse directe

$\prod_2^P$$NP \ne coNP$$NP$$\prod_2^P$

Noga Alon, coloriages restreints des graphiques