¿Es plausible una aceleración del no determinismo cuadrático de la computación determinista?

Este es un seguimiento de la aceleración no determinista del cálculo determinista .

¿Es plausible que el no determinismo (o una alternancia más general) permitiría una aceleración cuadrática general de la computación determinista? ¿O hay consecuencias inverosímiles conocidas para algo como ? $\mathsf{DTime}(n^2) \subseteq \mathsf{NTime}(n)$

cc.complexity-theory nondeterminism speed-up alternation tradeoff Kaveh
fuente

No estoy seguro, pero creo que con argumentos similares que utilizó en su pregunta anterior tenemos no está en . En realidad, no está en

, porque

, pero no conozco mejores límites inferiores.

T METRO S UNA T = {< una, X, 1^{norte}, 1^{t} >: \exists tu \in {0 0, 1}^{norte} s . t . {METRO}_{una} o tu t pags tu t s 1 o norte yo norte pags tu t < X, tu > w yo t h yo norte t s t mi pags s}

$\mathsf{TMSAT}=\{<a,x,1^n,1^t>:\exists u\in \{0,1\}^n\: s.t. \: M_a\: outputs\:1\: on\: input\: <x,u> \: within \: t \: steps \}$

D T I M E (n^{2} / \lg n)

$\mathsf{DTIME}(n^2/\lg{n})$

T M S A T

$\mathsf{TMSAT}$

D T I M E (n)

$\mathsf{DTIME}(n)$

N T I M E (n) \neq D T I M E (n)

$\mathsf{NTIME}(n)\neq\mathsf{DTIME}(n)$

Erfan Khaniki

@Erfan, mi argumento no muestra que no lo es, tampoco muestra que sea poco probable, solo muestra que demostrar que es desconocido y difícil para

ω (n \lg n)^{2}

$\omega(n\lg n)^2$ .

Kaveh

Sí, tiene usted razón. En realidad, este argumento muestra que es difícil demostrar

D T I M E (n^{2}) \subseteq N T I M E (n)

$\mathsf{DTIME}(n^2)\subseteq \mathsf{NTIME}(n)$ .

Erfan Khaniki

¿Es plausible una aceleración del no determinismo cuadrático de la computación determinista?

Respuestas: