Une accélération quadratique du non-déterminisme du calcul déterministe est-elle plausible?

Il s'agit d'un suivi de l'accélération non déterministe du calcul déterministe .

Est-il plausible que le non-déterminisme (ou plus généralement l'alternance) permette une accélération quadratique générale du calcul déterministe? Ou y a-t-il des conséquences invraisemblables connues pour quelque chose comme ? $\mathsf{DTime}(n^2) \subseteq \mathsf{NTime}(n)$

cc.complexity-theory nondeterminism speed-up alternation tradeoff Kaveh
la source

Je ne suis pas sûr mais je pense que par des arguments similaires que vous avez utilisés dans votre question précédente, nous avons

n'est pas dans

. En fait,

n'est pas dans

, parce que

, mais je ne connais pas de meilleures limites inférieures.

T M S A T = {< a, x, 1^{n}, 1^{t} >: \exists u \in {0, 1}^{n} s . t . M_{a} o u t p u t s 1 o n i n p u t < x, u > w i t h i n t s t e p 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

ω (n \lg n)^{2}

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

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

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

Une accélération quadratique du non-déterminisme du calcul déterministe est-elle plausible?

Réponses: