Niedeterministyczne przyspieszenie obliczeń deterministycznych

Czy niedeterminizm może przyspieszyć obliczenia deterministyczne? Jeśli tak to ile?

Przyspieszając obliczenia deterministyczne przez niedeterminizm rozumiem wyniki formy:

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

Np. Coś takiego

$\mathsf{DTime}(n^2) \subseteq \mathsf{NTime}(n)$

Jaki jest najbardziej znany wynik przyspieszenia obliczeń deterministycznych przez niedeterminizm? Co powiesz na $\mathsf{\Sigma^P_kTime}(n)$ a nawet $\mathsf{ATime}(n)$ zamiast $\mathsf{NTime}(n)$ ?

Załóżmy, że klasy złożoności są definiowane za pomocą maszyn Turinga z wieloma taśmami, aby uniknąć dobrze znanych osobliwości maszyn Turinga z subkwadratowym czasem.

Nie należy oczekiwać ekscytującego przyspieszenia. Mamy

a najbardziej znaną symulacją deterministycznego czasu w przestrzeni jest nadal twierdzenie Hopcroft – Paul – Valiant

Zatem nie wiadomo, czy niedeterminizm lub przemiana przyspieszają więcej niż czynnik logarytmiczny. (Podejrzewam, że nie jest znane przyspieszenie superliniowe, chociaż nie jestem pewien, czy nie można zmusić twierdzenia HPV do pracy z ATIME zamiast DSPACE.)

Istnieją dwie odrębne koncepcje:

(1) Wydajna symulacja maszyn deterministycznych przez maszyny niedeterministyczne.

(2) Wyniki przyspieszenia, które są uzyskiwane poprzez stosowanie symulacji w kółko.

Nie znam żadnej skutecznej symulacji maszyn deterministycznych przez maszyny niedeterministyczne, ale znam kilka wyników przyspieszenia, które można by wykorzystać, gdyby istniały wydajne symulacje.

Rozważ klasę języków, które są rozstrzygalne przez niedeterministyczną maszynę Turinga działającą przez czas t ( n ), używając tylko g ( n ) niedeterministycznych domysłów. Innymi słowy, długość świadka jest ograniczona przez g ( n ) .$NTIGU(t(n), g(n))$$t(n)$$g(n)$$g(n)$

Jeśli masz bardziej wydajną symulację, używając tylko niedeterministycznych domysłów, to wierzę, że możesz to przyspieszyć całkiem sporo. W szczególności uważam, że możesz udowodnić, co następuje:$\log(n)$

Jeśli , to D T I M E ( 2 $DTIME(n \log(n)) \subseteq NTIGU(n, \log(n))$$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".

Here is an explanation for why a general quartic nondeterministic speed-up of deterministic computation even if true would be hard to prove:

Assume that a general quartic nondeterministic speed-up of deterministic computation like $\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.)