Является ли вероятным ускорение квадратичного недетерминизма детерминированных вычислений?

Это продолжение недетерминированного ускорения детерминированных вычислений .

Возможно ли, что недетерминизм (или, в более общем смысле, чередование) позволил бы общее квадратичное ускорение детерминированных вычислений? Или есть какие-то известные неправдоподобные последствия для чего-то вроде ? $\mathsf{DTime}(n^2) \subseteq \mathsf{NTime}(n)$

cc.complexity-theory nondeterminism speed-up alternation tradeoff Кава
источник

Я не уверен, но я думаю, что с помощью аналогичных аргументов, которые вы использовали в предыдущем вопросе, мы имеем не находится в . На самом деле не находится в , потому что , но я не знаю лучших нижних границ.

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

Эрфан Ханики

@ Эрфан, мой аргумент не показывает, что это не так, он также не показывает, что это маловероятно, он просто показывает, что доказательство того, что оно неизвестно и трудно для .

ω (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)$

Эрфан Ханики

Ответы:

Обратите внимание, что даже результат, будет нарушать NSETH как одномерную полиномиальную идентичность тестирование (как определено в разделе 3.2) может быть решено за времени детерминистически, но, кажется, нет очевидного способа использовать недетерминизм, чтобы помочь доказать идентичность. $\mathsf{DTime}(\tilde{O}(n^2)) \subseteq \mathsf{NTime}(n^{2-\epsilon})$ $\tilde{O}(n^2)$

Джо Бебель
источник