Aceleración no determinista del cálculo determinista

¿Puede el no determinismo acelerar el cálculo determinista? Si es así, ¿cuánto?

Al acelerar el cálculo determinista por el no determinismo me refiero a los resultados de la forma:

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

Por ejemplo, algo como

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

¿Cuál es el resultado de aceleración más conocido del cálculo determinista por no determinismo? ¿Qué hay de $\mathsf{\Sigma^P_kTime}(n)$ o incluso $\mathsf{ATime}(n)$ en lugar de $\mathsf{NTime}(n)$ ?

Suponga que las clases de complejidad se definen utilizando máquinas de Turing de cinta múltiple para evitar las peculiaridades bien conocidas de las máquinas de Turing de cinta única de tiempo subcuadrático.

No debe esperar una aceleración emocionante. Tenemos

y la simulación más conocida del tiempo determinista por el espacio sigue siendo el teorema de Hopcroft-Paul-Valiant

Por lo tanto, no se sabe que el no determinismo o la alternancia aceleren en más de un factor logarítmico. (Sospecho que tampoco se conoce una aceleración superlineal, aunque no estoy seguro de si el teorema del VPH no puede funcionar con ATIME en lugar de DSPACE).

Hay dos conceptos distintos:

(1) Simulación eficiente de máquinas deterministas por máquinas no deterministas.

(2) Acelere los resultados que se obtienen aplicando una simulación una y otra vez.

No conozco ninguna simulación eficiente de máquinas deterministas por máquinas no deterministas, pero sí sé de varios resultados de aceleración que podrían usarse si existen simulaciones eficientes.

Considere la clase de lenguajes que son decidibles por una máquina Turing no determinista que se ejecuta por tiempo t ( n ) utilizando solo g ( n ) conjeturas no deterministas. En otras palabras, la longitud del testigo está limitada por g ( n ) .$NTIGU(t(n), g(n))$$t(n)$$g(n)$$g(n)$

Si tiene una simulación más eficiente usando solo conjeturas no deterministas, entonces creo que puede acelerarlo un poco. En particular, creo que puedes probar lo siguiente:$\log(n)$

Si , entonces D T I M E ( 2 $DTIME(n \log(n)) \subseteq NTIGU(n, \log(n))$.$DTIME(2^{\sqrt{n}}) \subseteq NTIME(n)$

Si encuentra esto interesante, entonces puedo escribir la prueba.

Ryan Williams introdujo algunas aceleraciones relacionadas en "Mejorar la búsqueda exhaustiva implica límites inferiores superpolinomiales".

Aquí hay una explicación de por qué sería difícil probar una aceleración no determinista cuántica general de la computación determinista, incluso si es verdadera:

Suponga que se cumple una aceleración no determinista cuántica general de la computación determinista como . En aras de la contradicción, suponga que S A T ∈ D T i m e ( o ( n 2 / lg n ) ) . Hay una reducción de tiempo cuadrático de cualquier problema en N T i m e ( $\mathsf{DTime}(n^4) \subseteq \mathsf{NTime}(n)$$\mathsf{SAT} \in \mathsf{DTime}(o(n^2/\lg n))$$\mathsf{NTime}(n)$$\mathsf{SAT}$$\mathsf{DTime}(n^4) \subseteq \mathsf{DTime}(o(n^4/\lg n))$

$\mathsf{SAT}$

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

$\mathsf{SAT}$

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