Quelles preuves avons-nous pour

17

Suite à la suggestion de Josh Grochow, je convertis mon commentaire d'une question précédente en une nouvelle question.

Quelles preuves avons-nous pour ?UPNP

Ici est la classe de langages reconnaissable par les machines de Turing non déterministes à temps polynomial qui ont un chemin d'acceptation unique sur les instances "oui" et aucun chemin d'acceptation sur les instances "non".UP

Évidemment , mais pourquoi penserions-nous que le confinement est strict? La preuve que je peux trouver est la séparation d'oracle : sous réserve d'un oracle aléatoire, . De plus, le Complexity Zoo suggère que \ mathsf {UP} ne semble pas avoir de problèmes complets.UPNPPUPNPUP

Sasho Nikolov
la source
6
Discussion connexe ici: cstheory.stackexchange.com/q/3887/1800
Hsien-Chih Chang 張顯 之
@ Hsien-ChihChang 張顯 之 hm, ma question est peut-être en double. Si vous le pensez, je peux le signaler pour suppression.
Sasho Nikolov
4
Je ne pense pas que ce soit un doublon. Je pense que les réponses à l'autre question compteraient comme des réponses à celle-ci, mais pas nécessairement l'inverse - il pourrait y avoir des raisons de croire qui ne sont pas de la forme " Si , alors une (autre) conséquence de mauvaise complexité se produit. " N P = U PNPUPNP=UP
Joshua Grochow
2
La meilleure preuve est que nous avons des limites supérieures sous-exponentielles sur certains problèmes naturels insolubles dans UP (tels que les versions de décision du logarithme discret et la factorisation entière) alors que nous ne sommes pas en mesure de trouver une telle limite supérieure pour certains problèmes NP-complets tels que 3SAT. Une telle borne supérieure pour 3SAT est impossible en supposant l'hypothèse du temps exponentiel.
Mohammad Al-Turkistany
1
@ MohammadAl-Turkistany: Mais ces problèmes sont dans , donc si , alors ils ne seront toujours que dans , donc ne serait pas -complet à moins que ...N P = U P N Pc o N P N P N P = c o N PUPcoUPNP=UPNPcoNPNPNP=coNP
Joshua Grochow

Réponses:

5

Même, Selman et Yacobi ont supposé qu'il n'existe pas de paire disjointe sorte que tous les séparateurs de soient -hard pour . Cette conjecture implique que .NP(UNE,B)(UNE,B)TpNPUPNP

S. Even, A. Selman et J. Yacobi. La complexité des problèmes de promesse avec les applications à la cryptographie à clé publique. Information et contrôle, 61: 159-173, 1984.

Mohammad Al-Turkistany
la source
1
Cela fonctionne également comme une bonne réponse pour le poste connexe cstheory.stackexchange.com/questions/3887/…
Mohammad Al-Turkistany
1
Cette conjecture forte implique également que . NPcoNP
Mohammad Al-Turkistany