Nicht deterministische Beschleunigung der deterministischen Berechnung

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

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

$\mathsf{DTime}(f(n)) \subseteq \mathsf{NTime}(n)$

ZB sowas

$\mathsf{DTime}(n^2) \subseteq \mathsf{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 ) ?$\mathsf{\Sigma^P_kTime}(n)$$\mathsf{ATime}(n)$$\mathsf{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.

Sie sollten keine aufregende Beschleunigung erwarten. Wir haben

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

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.)

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(n \log(n)) \subseteq NTIGU(n, \log(n))$, then $DTIME(2^{\sqrt{n}}) \subseteq 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".

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 $\mathsf{DTime}(n^4) \subseteq \mathsf{NTime}(n)$ holds. For the sake of contradiction, assume that $\mathsf{SAT} \in \mathsf{DTime}(o(n^2/\lg n))$. There is a quadratic-time reduction from any problem in $\mathsf{NTime}(n)$ to $\mathsf{SAT}$. Combining these we would have $\mathsf{DTime}(n^4) \subseteq \mathsf{DTime}(o(n^4/\lg n))$ contradicting the time hierarchy theorem.

Therefore, a general quartic nonterministic speed-up of deterministic computation would imply a lower-bound for $\mathsf{SAT}$:

$\mathsf{DTime}(n^4) \subseteq \mathsf{NTime}(n) \to \mathsf{SAT} \notin \mathsf{DTime}(o(n^2/\lg n))$.

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

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

$\mathsf{DTime}(f(n^2)) \subseteq \mathsf{NTime}(n) \to \mathsf{SAT} \notin \mathsf{DTime}(o(f(n)/\lg n))$.

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