Ist eine quadratische Nichtdeterminismus-Beschleunigung der deterministischen Berechnung plausibel?

9

Dies ist eine Folge der nicht deterministischen Beschleunigung der deterministischen Berechnung .

Ist es plausibel, dass Nichtdeterminismus (oder allgemeiner Wechsel) eine allgemeine quadratische Beschleunigung der deterministischen Berechnung ermöglichen würde? Oder gibt es bekannte unplausible Konsequenzen für etwas wie ?DTime(n2)NTime(n)

Kaveh
quelle
Ich bin mir nicht sicher, aber ich denke, durch ähnliche Argumente, die Sie in Ihrer vorherigen Frage verwendet haben, haben wir ist nicht in D T I M E ( n 2 / lg n ) . Tatsächlich ist T M S A T nicht in D T I M E ( n ) , weil N T I M E ( n ) D T I M E ( n ) , aber ich kenne keine besseren Untergrenzen.
TMSAT={<a,x,1n,1t>:u{0,1}ns.t.Maoutputs1oninput<x,u>withintsteps}
DTIME(n2/lgn)TMSATDTIME(n)NTIME(n)DTIME(n)
Erfan Khaniki
@Erfan, mein Argument zeigt nicht, dass es nicht ist, es zeigt auch nicht, dass es unwahrscheinlich ist, es zeigt nur, dass der Beweis, dass es unbekannt und schwierig für . ω(nlgn)2
Kaveh
Ja, du hast recht. Tatsächlich zeigt dieses Argument, dass es schwierig ist, zu beweisen . DTIME(n2)NTIME(n)
Erfan Khaniki

Antworten:

10

DTime(O~(n2))NTime(n2ϵ)O~(n2)

Joe Bebel
quelle