Недетерминированное ускорение детерминированных вычислений

Может ли недетерминизм ускорить детерминистские вычисления? Если да, то сколько?

Под ускорением детерминированных вычислений недетерминизмом я подразумеваю результаты вида:

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

Например, что-то вроде

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

Каков наиболее известный результат ускорения детерминированных вычислений с помощью недетерминизма? Что насчет или даже A T i m e ( n ) вместо N T i m e ( n $\mathsf{\Sigma^P_kTime}(n)$$\mathsf{ATime}(n)$$\mathsf{NTime}(n)$ ?

Предположим, что классы сложности определяются с использованием многоленточных машин Тьюринга, чтобы избежать хорошо известных особенностей одноленточных машин Тьюринга с субквадратичным временем.

Вы не должны ожидать захватывающего ускорения. У нас есть

и самое известное моделирование детерминированного времени пространством - все еще теорема Хопкрофта-Пола-Валианта

Таким образом, не определено, что недетерминизм или чередование ускоряют более чем логарифмический фактор. (Я подозреваю, что суперлинейное ускорение также не известно, хотя я не уверен, что теорема HPV не может работать с ATIME вместо DSPACE.)

Есть две разные концепции:

(1) Эффективное моделирование детерминированных машин недетерминированными машинами.

(2) Ускорение результатов, которые получены путем применения моделирования снова и снова.

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

Рассмотрим класс языков, которые разрешимы недетерминированной машиной Тьюринга, работающей в течение времени t ( n ), используя только g ( n ) недетерминированных догадок. Другими словами, длина свидетеля ограничена g ( n ) .$NTIGU(t(n), g(n))$$t(n)$$g(n)$$g(n)$

Если у вас есть более эффективное моделирование, используя только $\log(n)$ недетерминированные догадки, то, я думаю, вы можете немного ускорить его. В частности, я считаю, что вы можете доказать следующее:

Если , то D T I M E ( 2 $DTIME(n \log(n)) \subseteq NTIGU(n, \log(n))$.$DTIME(2^{\sqrt{n}}) \subseteq NTIME(n)$

Если вам это интересно, я могу написать доказательство.

Райан Уильямс представил некоторые связанные ускорения в «Улучшение исчерпывающего поиска подразумевает суперполиномиальные нижние границы».

Вот объяснение того, почему общее квартетическое недетерминированное ускорение детерминированных вычислений, даже если истинно, будет трудно доказать:

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

$\mathsf{SAT}$$\mathsf{NTime}(n)$$f(n)/\lg n$$k\geq 2$$\lg n$