Welche Beweise haben wir für ?

17

Ich folge dem Vorschlag von Josh Grochow und wandle meinen Kommentar von einer vorherigen Frage in eine neue Frage um.

Welche Beweise haben wir für ?UP≠NP

Hier ist die Klasse von Sprachen, die durch nicht deterministische Polynomzeit-Turing-Maschinen erkennbar sind, die einen eindeutigen Akzeptanzpfad für "yes" -Instanzen und einen eindeutigen Akzeptanzpfad für "no" -Instanzen haben.UP

Offensichtlich , aber warum sollten wir glauben , dass die Eindämmung streng ist? Die Beweise , die ich finden kann , ist Oracle Trennung : nach einem zufälligen Orakel, . Der Complexity Zoo legt außerdem nahe, dass es bei vermutlich keine vollständigen Probleme gibt.P ⊊ U P ⊊ N P U PUP⊆NPP⊊UP⊊NPUP

cc.complexity-theory complexity-classes conditional-results unique-solution Sasho Nikolov
quelle
6
Zugehörige Diskussion hier: cstheory.stackexchange.com/q/3887/1800
Hsien-Chih Chang 張顯 之
@ Hsien-ChihChang 張顯 張顯 hm, vielleicht ist meine Frage doppelt. Wenn Sie so denken, kann ich es zum Löschen markieren.
Sasho Nikolov
4
Ich denke nicht, dass dies ein Duplikat ist. Ich würde denken, dass Antworten auf die andere Frage als Antworten auf diese Frage gelten, aber nicht unbedingt umgekehrt - es könnte Gründe geben zu glauben, dass nicht von der Form ist " Wenn , tritt eine (andere) schlechte Komplexitätsfolge auf. " N P = U PNP≠UPNP=UP
Joshua Grochow
2
Der beste Beweis ist, dass wir subexponentielle Obergrenzen für einige natürliche schwer zu lösende Probleme in UP haben (wie die Entscheidungsversionen des diskreten Logarithmus und der ganzzahligen Faktorisierung), während wir eine solche Obergrenze für bestimmte NP-vollständige Probleme wie nicht finden können 3SAT. Eine solche Obergrenze für 3SAT ist unter der Annahme der Exponentialzeithypothese unmöglich.
Mohammad Al-Turkistany
1
@ MohammadAl-Turkistany: Aber diese Probleme liegen in . Wenn also , dann liegen sie immer noch nur in , wäre also erst dann -vollständig, wenn ...N P = U P N P ∩ C O N P N P N P = c o N PUP∩coUPNP=UPNP∩coNPNPNP=coNP
Joshua Grochow

Antworten:

5

Sogar Selman und Yacobi vermuteten, dass es kein disjunktes Paar so dass alle Separatoren von für sind . Diese Vermutung impliziert, dass .( A , B ) ( A , B ) ≤ P T N P U P ≠ N PNP(A,B)(A,B)≤TpNPUP≠NP

S. Even, A. Selman und J. Yacobi. Die Komplexität der Versprechen Probleme mit Anwendungen für die Kryptographie mit öffentlichen Schlüsseln. Information and Control, 61: 159–173, 1984.

Mohammad Al-Turkistany
quelle
1
Dies funktioniert auch als gute Antwort für den zugehörigen Beitrag cstheory.stackexchange.com/questions/3887/…
Mohammad Al-Turkistany
1
Diese starke Vermutung impliziert auch, dass . NP≠coNP
Mohammad Al-Turkistany