Существуют ли естественные разделения в недетерминированной иерархии времени?

Первоначальная теорема недетерминированной временной иерархии принадлежит Кук (ссылка на С. Кука, иерархия недетерминированной временной сложности , JCSS 7 343–353, 1973). Теорема утверждает, что для любых действительных чисел $r_1$ и $r_2$ , если $1 \le r_1 \lt r_2$ то NTIME ( $n^{r_1}$ ) строго содержится в NTIME ( $n^{r_2}$ ).

Одна ключевая часть доказательства использует (неуказанную) диагонализацию для построения разделяющего языка от элементов меньшего класса. Это не только неконструктивный аргумент, но языки, полученные диагонализацией, обычно не дают никакого понимания, кроме самого разделения.

Если мы хотим понять структуру иерархии NTIME, вероятно, необходимо ответить на следующий вопрос:

Есть ли естественный язык в NTIME ( ), но нет в NTIME ( n k )?$n^{k+1}$$n^k$

Одним из кандидатов может быть k-ISOLATED SAT , что требует нахождения решения для формулы CNF без других решений в пределах расстояния Хэмминга k. Однако, доказав нижнюю границы кажется это сложно, как обычно. Очевидно, что проверка k-шара Хэмминга не связана с потенциальными решениями, которые «должны» требовать проверки различных назначений, но это отнюдь не легко доказать . (Примечание: Райан Уильямс указывает, что эта нижняя граница для k- ИЗОЛИРОВАННОГО SAT фактически докажет P ≠ NP, поэтому эта проблема не является подходящим кандидатом.)$\Omega(n^k)$$k$

Обратите внимание, что теорема верна безоговорочно, независимо от недоказанных разделений, таких как P против NP. Таким образом, утвердительный ответ на этот вопрос не разрешит P против NP, если только он не обладает дополнительными свойствами, такими как ИЗОЛИРОВАННОЕ SAT выше. $k$ Естественное разделение NTIME, возможно, поможет осветить часть «трудного» поведения NP, части, которая возникает из-за бесконечной возрастающей последовательности твердости.

Поскольку нижние границы жесткие, я приму в качестве ответа естественные языки, для которых у нас может быть веская причина полагать нижнюю границу, хотя доказательств еще может не быть. Например, если бы этот вопрос был о DTIME, то я бы принял -CLIQUE для неубывающей функции f ( x ) ∈ Θ ( x ) , как естественный язык, который, вероятно, обеспечивает необходимые разделения, на основе схем нижних границ Разборов х и Rossman в и п 1 - ε -inapproximability из CLIQUE.$f(k)$$f(x) \in \Theta(x)$$n^{1-\epsilon}$

(Отредактировано с учетом комментария Каве и ответа Райана.)

Насколько я знаю, мы не знаем о таких языках, или, если мы знаем, существует значительный спор о «естественности» их. Я знаю, что это не совсем удовлетворительный ответ, но я могу сказать:

(а) Если доказать время нижняя граница для к-ИЗОЛИРОВАННОЕ SAT для каждого к , то вы на самом деле доказано P ≠ N P .$\Omega(n^k)$$k$$P \neq NP$

(b) Один из способов показать, что k-ИЗОЛИРОВАННАЯ САТ является одной из этих естественных проблем в - показать, что k-ИЗОЛИРОВАННАЯ Проблема SAT является сложной (в обычном, формальном смысле наличия эффективных сокращений) для N T I M E [ n k ] . На самом деле это единственный способ, которым мы знаем, как доказать такие результаты. Но k-ISOLATED SAT, вероятно, не сложно в этом смысле, есть некоторые очень маловероятные последствия.$NTIME[n^{k+1}] - NTIME[n^k]$$NTIME[n^k]$

Основная причина в том , что к-единичные случаи SAT разрешимы в , независимо от к . Вы можете экзистенциально угадать изолированное присвоение, а затем повсеместно проверить (для всех O ( log ( ∑ k i = 1 ($\Sigma_2 TIME[n]$$k$способы переключения доkбитов в назначении), что ни одно из других «локальных» назначений не работает.$O(\log (\sum_{i=1}^k {n \choose i}))$$k$

Вот доказательство части (а). Пусть ISOLATED SAT будет версией проблемы с заданным как часть ввода (скажем, в унарном). Предположим, что мы доказали, что для ISOLATED SAT требуется время Ω ( n k ) для всех k . Если Р = Н Р , то Σ 2 Т Я М Е [ п ] в T I M E [ п с ] при некоторых фиксированных с (доказательство использует эффективный вариант теоремы Кука: если есть алгоритм СБ работает во время н $k$$\Omega(n^k)$$k$$P=NP$$\Sigma_2 TIME[n]$$TIME[n^c]$$c$$n^d$, тогда достаточно любого ). Но мы доказали, что в Σ 2 T I M E [ n ] есть язык , которого нет в T I M E [ n k ] для каждого k . Это противоречие, поэтому P ≠ N P .$c > d^2$$\Sigma_2 TIME[n]$$TIME[n^k]$$k$$P \neq NP$

Вот доказательство части (б). Если бы каждый мог быть эффективно сведен к k-ИЗОЛИРОВАННОЙ SAT-формуле (например, все n- битные экземпляры L сводятся к k -ИЗОЛИРОВАННЫМ SAT-формулам не более чем f ( k ) n c размер) тогда N P = ⋃ k N T I M E [ n k ] ⊆ Σ 2 T I M E $L \in NTIME[n^k]$$n$$L$$k$$f(k) n^{c}$ . Это непосредственно вытекает C уплотнительное N P ≠ N P , но кроме тогоон выглядит очень маловероятночто все N P может быть смоделирована так эффективно в полиномиальной иерархии.$NP=\bigcup_{k} NTIME[n^k] \subseteq \Sigma_2 TIME[n^{c+1}]$$coNP \neq NP$$NP$