als Orakel

12

Tut NPNPcoNP=NPhalten?

Klar NPNPNP , aber es scheint mir, dass NPcoNP "deterministisch" ist, was mich glauben lässt, dass dies wahr ist.

Gibt es einen einfachen Beweis (oder vielleicht nur per Definition)?

maomao
quelle
6
Erstens ja. In der Tat erfüllt ein Orakel genau dann N P A = N P, wenn A N Pc o N P ist . Diese Klasse heißt L o w ( N P ) oder manchmal L 1 P : complexityzoo.uwaterloo.ca/Complexity_Zoo:L#lkp . Zweitens denke ich, dass es überhaupt nicht klar ist, dass N P N PN PANPA=NPANPcoNPLow(NP)L1PNPNPNP , obwohl dies ein weit verbreiteter Glaube ist. Insbesondere impliziert es PNPund scheint strikt stärker zu sein, da es keine relativierbare Implikation gibt.
Joshua Grochow
2
Auch Menschen, die glauben, dass FACTORING schwierig ist, könnten Ihre Intuition in Frage stellen, dass "deterministisch" ist. NPcoNP
Niel de Beaudrap
9
@JoshuaGrochow: Ich denke, Sie sollten das als Antwort hinzufügen, mit einigen Erläuterungen dazu, was die Klassen in der niedrigen Hierarchie sind. Es ist ungefähr so ​​gut wie die Antwort, die das OP wahrscheinlich erhalten wird.
Niel de Beaudrap
2
enthält c o - N P , was möglicherweise erklärt, warum es unwahrscheinlich ist, dass es N P entspricht . NPNPcoNPNP
Domotorp
4
@NieldeBeaudrap: Ich zögerte, es als Antwort und nicht als Kommentar zu veröffentlichen. Obwohl ich glaube, dass Maomao diese Frage wirklich ernsthaft gestellt hat, kann und wurde sie in der Vergangenheit als Hausaufgabe gegeben.
Joshua Grochow

Antworten:

13

Ja. In der Tat erfüllt ein Orakel genau dann N P A = N P, wenn A N Pc o N P ist . Diese Klasse wird L o w ( N P ) oder manchmal L 1 P genannt (siehe den Link und das dort zitierte Papier für eine genauere Erklärung der niedrigen Hierarchie im Allgemeinen).ANPA=NPANPcoNPLow(NP)L1P

Ihre Intuition über "Determinismus" ist tatsächlich etwas richtig (obwohl sie nicht deterministisch genug ist, um zu folgern, dass ). Versuchen Sie dies als eine Übung , und Sie werden diese Intuition sehen rehabilitiert: erste Show - sorgfältig, um die Details Buchstabieren - , dass , wenn A P , dann N P A = N P . Finden Sie genau den Teil Ihres Beweises heraus, der nicht funktioniert, wenn Sie nur A N P annehmen , und stellen Sie dann fest, warum dieser Teil funktioniert, wenn A N PP=NPcoNPAPNPA=NPANP .ANPcoNP

(Das Gegenteil zu zeigen ist auch nicht allzu schwierig: impliziert A N Pc o N P. )NPA=NPANPcoNP

Joshua Grochow
quelle