Implikationen zwischen

Wenn wir beweisen können, dass , bedeutet dies, dass ? $\mathsf{L}=\mathsf{P}$ $\mathsf{NL}=\mathsf{NP}$

Ich dachte, dass es der Fall ist, aber ich kann es nicht beweisen (auch für das Gegenteil).

cc.complexity-theory complexity-classes nondeterminism Thatchaphol
quelle

Das Gegenteil zu

beweisen

Das Gegenteil läuft darauf hinaus, ob NL = P L = P impliziert. Dies gilt nicht unbedingt, es sei denn, L = NL.

Mohammad Al-Turkistany

Ich habe eine verwandte Frage zu den Beziehungen zwischen P gegen L, NP gegen NL, BPP gegen BPL, vsP gegen ⊕L gestellt. Wenn Sie interessiert sind, schauen Sie bitte vorbei. Vielen Dank! cstheory.stackexchange.com/questions/31073/…

Michael Wehar

Antworten:

Nein. Es ist möglich, dass L = P und P! = NP, was impliziert, dass NL! = NP ist, da NL in P enthalten ist.

Mohammad Al-Turkistany
quelle

Ich denke, es wäre wahrscheinlich hilfreich, anstatt nur dies direkt zu behaupten, eine gewisse Intuition zu geben, wie dies sein könnte. Wenn man die Konstruktion NP = ∃P betrachtet (dh ihre Definition in Bezug auf die Überprüfung eines Zeugen unter Verwendung eines Polytime-Algorithmus), kann ich sehen, wie man vermuten könnte , dass wir bei P = L einfach NP = ∃L = NL durch Substitution erhalten könnten . Vielleicht helfen einige Anmerkungen dazu, wie die logarithmische Einschränkung auf dem Arbeitsband darauf hinweisen würde, warum dies nicht der Fall ist.

Niel de Beaudrap