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

9

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

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

Кава
источник
Я не уверен, но я думаю, что с помощью аналогичных аргументов, которые вы использовали в предыдущем вопросе, мы имеем не находится в . На самом деле не находится в , потому что , но я не знаю лучших нижних границ.
TMSAT={<a,x,1n,1t>:u{0,1}ns.t.Maoutputs1oninput<x,u>withintsteps}
DTIME(n2/lgn)TMSATDTIME(n)NTIME(n)DTIME(n)
Эрфан Ханики
@ Эрфан, мой аргумент не показывает, что это не так, он также не показывает, что это маловероятно, он просто показывает, что доказательство того, что оно неизвестно и трудно для . ω(nlgn)2
Каве
Да ты прав. На самом деле этот аргумент показывает, что трудно доказать . DTIME(n2)NTIME(n)
Эрфан Ханики

Ответы:

10

Обратите внимание, что даже результат, будет нарушать NSETH как одномерную полиномиальную идентичность тестирование (как определено в разделе 3.2) может быть решено за времени детерминистически, но, кажется, нет очевидного способа использовать недетерминизм, чтобы помочь доказать идентичность.DTime(O~(n2))NTime(n2ϵ)O~(n2)

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