Nicht deterministische Beschleunigung der deterministischen Berechnung

14

Kann Nichtdeterminismus die deterministische Berechnung beschleunigen? Wenn ja, wie viel?

Mit Beschleunigung der deterministischen Berechnung durch Nichtdeterminismus meine ich Ergebnisse der Form:

DTime(f(n))NTime(n)

ZB sowas

DTime(n2)NTime(n)

Was ist das bekannteste Beschleunigungsergebnis der deterministischen Berechnung durch Nichtdeterminismus? Was ist mit oder sogar A T i m e ( n ) anstelle von N T i m e ( n ) ?ΣkPTime(n)ATime(n)NTime(n)

Nehmen Sie an, dass Komplexitätsklassen mit Turing-Maschinen mit mehreren Bändern definiert werden, um die bekannten Besonderheiten der Turing-Maschinen mit subquadratischer Zeit und einzelnem Band zu vermeiden.

Kaveh
quelle
3
(Von Satz 4.1 und der Zeithierarchie Theorem, kann Ihr Beispiel nicht für 1-Band TMs halten.)

Antworten:

11

Sie sollten keine aufregende Beschleunigung erwarten. Wir haben

DTIME(f(n))NTIME(f(n))ATIME(f(n))DSPACE(f(n)),

und die bekannteste Simulation deterministischer Zeit durch Raum ist immer noch der Hopcroft-Paul-Valiant-Satz

DTIME(f(n))DSPACE(f(n)/logf(n)).

Es ist daher nicht bekannt, dass Nichtdeterminismus oder Alternation eine Beschleunigung um mehr als einen logarithmischen Faktor bewirken. (Ich vermute, dass auch keine superlineare Beschleunigung bekannt ist, obwohl ich nicht sicher bin, ob das HPV-Theorem nicht mit ATIME anstelle von DSPACE funktioniert.)

Emil Jeřábek unterstützt Monica
quelle
1
Bei One-Tape-Online-Turingmaschinen ist es folkloristisch, dass . NTIME(n)DSPACE(n)
Michael Wehar
1
For two-tape Turing machines, we have DTIME(n)DSPACE(n/log(n)) as stated above.
Michael Wehar
2
The question is about multitape Turing machines.
Emil Jeřábek supports Monica
4
I just wanted to provide additional clarification for the interested reader.
Michael Wehar
2
Nach Paul-Pippenger-Szemerédi-Trotter lautet die erste Einbeziehung für den Sonderfall f ( n ) = n . DTIME(f(n))NTIME(f(n))f(n)=n
András Salamon
6

Es gibt zwei unterschiedliche Konzepte:

(1) Effiziente Simulation deterministischer Maschinen durch nicht deterministische Maschinen.

(2) Beschleunigen Sie die Ergebnisse, die durch wiederholtes Anwenden einer Simulation erzielt werden.

Ich kenne keine effiziente Simulation deterministischer Maschinen durch nicht deterministische, aber ich kenne mehrere Beschleunigungsergebnisse, die verwendet werden könnten, wenn effiziente Simulationen existieren.

Betrachten wir die Klasse der Sprachen , die entscheidbar durch eine nicht-deterministischen Turing Maschine laufen für t ( n ) Zeit nur mit g ( n ) nicht-deterministischen Vermutungen. Mit anderen Worten ist die Zeugenlänge durch g ( n ) begrenzt .NTIGU(t(n),g(n))t(n)g(n)g(n)

If you have a more efficient simulation using only log(n) non-deterministic guesses, then I believe you can speed it up quite a bit. In particular, I believe you can prove the following:

If DTIME(nlog(n))NTIGU(n,log(n)), then DTIME(2n)NTIME(n).

If you find this interesting, then I can write-up the proof.

Ryan Williams introduced some related speed-ups in "Improving Exhaustive Search Implies Superpolynomial Lower Bounds".

Michael Wehar
quelle
1
As you can see, DTIME(nlog(n))NTIGU(n,log(n)) is a rather big assumption and it is quite reasonable that you could prove the hypothesis to be false. Let me know if you do. :)
Michael Wehar
@AndrasSalamon : ​ How does that follow from exhaustive search? ​ ​ ​ ​
@RickyDemer you are right, it does not; have removed the comments. I was implicitly assuming that the nondeterminism was at the end of the computation, but it should be assumed to be at the beginning.
András Salamon
Update: Endlich begann ich mit dem Aufschreiben des vorgeschlagenen Beschleunigungsergebnisses. Es scheint ein bisschen anders zu sein als andere Beschleunigungsergebnisse, die ich gefunden habe. Bitte zögern Sie nicht, mir zu antworten oder eine E-Mail zu senden, wenn Sie an einer Diskussion interessiert sind. Vielen Dank! :)
Michael Wehar
1
würde auf jeden Fall einen Blick darauf werfen, das ist ein faszinierender Ansatz.
András Salamon
6

Hier ist eine Erklärung dafür, warum eine allgemeine quartal-nicht-deterministische Beschleunigung der deterministischen Berechnung selbst dann schwer zu beweisen ist, wenn sie wahr ist:

Nehmen wir an, dass eine allgemeine quartische nichtdeterministische Beschleunigung der deterministischen Berechnung ähnlich ist DTime(n4)NTime(n) holds. For the sake of contradiction, assume that SATDTime(o(n2/lgn)). There is a quadratic-time reduction from any problem in NTime(n) to SAT. Combining these we would have DTime(n4)DTime(o(n4/lgn)) contradicting the time hierarchy theorem.

Therefore, a general quartic nonterministic speed-up of deterministic computation would imply a lower-bound for SAT:

DTime(n4)NTime(n)SATDTime(o(n2/lgn)).

Therefore proving a general quadratic nondeterministic speed-up of deterministic computation is at least as hard as proving almost quadratic lower-bounds on SAT.

Similarly, for any well-behaving function f(n):

DTime(f(n2))NTime(n)SATDTime(o(f(n)/lgn)).

(If in place of SAT we pick a problem which is hard for NTime(n) under linear-time reductions then this would give f(n)/lgn lower bound for that problem. If we fix the number of the machine tapes to some k2 then we can use Fürer's time hierarchy theorem which does not have the lgn factor.)

Kaveh
quelle
Since we don't even know that SAT is not in DTime(n), we don't know an ω(nlgn)2 speed-up.
Kaveh