Насколько быстрым должен быть недетерминированный алгоритм для полной задачи EXPTIME, чтобы подразумевать

Насколько быстрым должен быть недетерминированный алгоритм для полной задачи EXPTIME, чтобы подразумевать $P \neq NP$ ? Недетерминирован алгоритм полиномиальное время будет немедленно следует это потому , что $P \neq EXPTIME$ , но никто не считает , $NP = EXPTIME$ . Если бы я сделал алгебру правильно (см. Ниже), теорема иерархии времени все равно дала бы значение $P \neq NP$ для $O(2^n/f(n))$ время выполнения для любого суперполинома$f(\cdot)$ , но для всех, кого я знаю, есть полные проблемы с эффективными сокращениями, которые позволяют более медленным алгоритмам давать результат. Существуют ли EXPTIME-полные проблемы, когда мы знаем что-то вроде$2^n/n$ или$2^n/n^2$ с недетерминизмом достаточно?

Уточнение «алгебры»: $P = NP$ подразумевает $EXPTIME=NEXPTIME$ аргументом заполнения, поэтому недетерминированный алгоритм $2^n/f(n)$ для задачи, полной EXPTIME также будет один для NEXPTIME-полной проблемы. Для суперполинома $f(\cdot)$ это противоречило бы недетерминированной теореме иерархии времени, так как мы могли бы уменьшить, используя некоторый $L \in$ NTIME$(2^n)$ .

Я думаю, что это легче перевернуть.

Если P = N P , то N T I M E ( T ( n ) ) ⊂ D T I M E ( ( T ( n ) ) c ) для некоторой константы c и любого T ( n ) > n . Поскольку D T I M E ( ( T ( n ) c ) не содержит $\mathsf{P}=\mathsf{NP}$$\mathsf{NTIME}(T(n)) \subset \mathsf{DTIME} ((T(n))^c)$$c$$T(n) > n$$\mathsf{DTIME} ((T(n)^c)$T I M E ( T ( n ) c log T ( n ) ) ⊂ D T I M E ( T ( n ) c + 1 ) , это означает, что мы не можем решить, скажем, все проблемы в D T I M E ( 2 n ) в N T I M E ( 2 ϵ n ) для некоторого$\mathsf{DTIME}(T(n)^{c}\log T(n)) \subset \mathsf{DTIME}(T(n)^{c+1})$$\mathsf{DTIME}(2^n)$$\mathsf{NTIME} (2^{\epsilon n})$$\epsilon$, Таким образом , не-детерминированным времени 2 O ( п ) алгоритм для задачи полной для D T I M E ( 2 л ) при квазилинейных сокращений будет достаточно , чтобы доказать P ≠ N P .$2^{o(n)}$$\mathsf{DTIME} (2^n)$$\mathsf{P} \neq \mathsf{NP}$

Простой ответ: Для каждой задачи E X P T I M E - h a r d существует некоторая постоянная c, такая, что если бы мы могли решить задачу в N T I M E ( 2 o ( n $EXPTIME$$hard$$c$с )), тоР≠НР.$NTIME(2^{o(n^{\frac{1}{c}})})$$P \neq NP$

Примечание. Константа c исходит от увеличения размера экземпляра, которое является результатом сокращений.$c$

Основание: Пусть Х обозначают E X P T I M E - час г д проблем. Это означает , что каждая проблема в E X P T I M E является многочленом время сводится к X . На самом деле, мы можем показать больше.$X$$EXPTIME$$hard$$EXPTIME$$X$

Задача принятия для 2 n ограниченных по времени детерминированных машин Тьюринга находится в D T I M E ( n ⋅ 2 n ) ⊆ E X P T I M E и, следовательно, сводится к X за полиномиальное время .$2^n$$DTIME(n \cdot 2^n) \subseteq EXPTIME$$X$

Следовательно, должна быть некоторая фиксированная константа c, такая, что каждая задача в D T I M E ( 2 n ) сводится за полиномиальное время к X, где увеличение размера экземпляра равно O ( n c ) . То есть, экземпляры размера п сводятся к случаям размера O ( п с ) для X .$c$$DTIME(2^n)$$X$$O(n^c)$$O(n^c)$$X$

Теперь, если бы мы имели X ∈ N T I M E ( 2 o ( n 1c )), тоDTIME(2n)⊆NTIME(2o(n)). Однако это подразумеваетP≠NP(подробности см. Ниже).$X \in NTIME(2^{o(n^{\frac{1}{c}})})$$DTIME(2^n) \subseteq NTIME(2^{o(n)})$$P \neq NP$

Дополнительные подробности: Можно показать , что Р = Н Р ⇔ ∃ с ' ∀ к Н Т Я М Е ( п к ) ⊆ D Т Я М Е ( п с ' к ) .$P=NP$ $\Leftrightarrow$ $\exists c^{\prime}$ $\forall k$ $NTIME(n^k) \subseteq DTIME(n^{c^{\prime}k})$

Другими слова, если вы можете решить N P - гр уплотнительного т р л х т е задачи за полиномиальное время, то существует единый способ ускорения любой проблемы в N P .$NP$$complete$$NP$

Теперь, давайте предположим , что P = N P . По предыдущему (с k = 1) мы получаем постоянную c ′ такую, что N T I M E ( n ) ⊆ D T I M E ( n c ′ ) $P=NP$$k$$c^{\prime}$

Затем мы можем использовать заполнение, чтобы увеличить это включение и получить

Тогда по теореме детерминированной иерархии времени имеем N T I M E ( 2 n ) ⊆ D T I M E ( 2 c ′ n ) ⊊ D T I M E ( 2 ( c ′ + ϵ ) n ) для любого ε > 0 .

Следовательно, мы не можем иметь $DTIME(2^{(c^{\prime}+\epsilon)n}) \subseteq NTIME(2^{n}).$

Кроме того, мы не могли бы иметь D T I M E ( 2 n ) ⊆ N T I M E ( 2 o ( n ) ), потому что при заполнении мы получили бы D T I M E ( 2 ( c ′ + ϵ ) n ) ⊆ N Т Я М Е ( 2 о ( п ) ) .$DTIME(2^{n}) \subseteq NTIME(2^{o(n)})$$DTIME(2^{(c^{\prime}+\epsilon)n}) \subseteq NTIME(2^{o(n)})$

Далее Вопрос: Есть ли какие - либо простые примеры E X P T I M E - с о т р л е т е проблем , где мы можем легко определить размер экземпляра раздутие постоянной C ?$EXPTIME$$complete$$c$