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

Верно ли, что в полиномиальной иерархии существуют проблемы, разрешимые во времени (с помощью чередующейся машины Тьюринга на некотором уровне полиномиальной иерархии), которые не разрешимы в на любом уровне полиномиальная иерархия? Другими словами - существует ли теорема временной иерархии для полиномиальной иерархии, как это существует для P и NP? Если есть - ссылка была бы отличной. $O(n^k)$ $O(n^{k-1})$

Сложность, с которой я столкнулся, состоит в том, что имитирующая машина при моделировании машин со всех уровней иерархии не находится ни на каком отдельном уровне иерархии. Что приводит к смежному вопросу - к какому наименьшему классу относится такой симулятор? Есть ли смысл определять класс с чередованиями (или / )? $O(n)$ $O(\log n)$ $O(\log \log n)$

cc.complexity-theory reference-request polynomial-hierarchy time-hierarchy Джозеф
источник

Использование линейного числа чередований дает вам PSPACE, поскольку квантифицированная логическая формула является PSPACE-полной.

Деррик Столи

Ответы:

Да. Например, обычные доказательства теоремы временной иерархии (путем непосредственного моделирования произвольных машин) могут быть использованы , чтобы показать , что для каждого , не является подмножеством . Причина перехода от к $c \geq 1$ $\Sigma_c TIME[n^k]$ $\Pi_c TIME[n^{k-1}]$ $\Sigma$ $\Pi$ в том, что в этом аргументе диагонализации мы должны сделать «противоположность» машине, которую мы моделируем, поэтому мы должны работать в универсальном режиме, когда симулятор находится в экзистенциальном режиме, и наоборот.

Кроме того, можно получить результат , как это без переключения от до : для каждого , не является подмножество . Это можно сделать, используя доказательство иерархии времени из-за Зака (ссылка: « Иерархия времени машины Тьюринга », Теоретическая информатика 26 (3): 327--333, 1983). Для явной ссылки на эту версию теоремы иерархии времени, см. Дитер ван Мелкебек $\Sigma$ $\Pi$ $c \geq 1$ $\Sigma_c TIME[n^k]$ $\Sigma_c TIME[n^{k-1}]$ « Обзор нижних границ для удовлетворения и связанных с этим проблем » (доступно на его домашней странице).

Райан Уильямс
источник

Этот ответ очень ясно демонстрирует существование теоремы иерархии времени для каждого отдельного уровня иерархии. Это не сразу указывает на наличие такой теоремы для PH в целом.

Джозеф

Ваш более сильный вопрос будет трудно решить утвердительно; это будет означать

. Предположим, что есть

и язык

, которого нет в

для каждого

. Тогда

L O G S P A C E \neq N P

$LOGSPACE \neq NP$

c

$c$

L

$L$

Σ_{c} T I M E [n^{k}]

$\Sigma_c TIME[n^k]$

Σ_{d} T I M E [n^{k - 1}]

$\Sigma_d TIME[n^{k-1}]$

d

$d$

L O G S P A C E \neq N P

$LOGSPACE \neq NP$ , Это потому, что каждый язык

находится в

для некоторого

зависящего от

(по аргументу типа теоремы Савича). Поэтому, если

то фактически каждый язык в

находится в

L \in L O G S P A C E

$L \in LOGSPACE$

Σ_{d} T I M E [n^{2}]

$\Sigma_d TIME[n^2]$

d

$d$

L

$L$

L O G S P A C E = N P

$LOGSPACE = NP$

Σ_{c} T I M E [n^{k}]

$\Sigma_c TIME[n^k]$

длянекоторого

, противоречащего тому, что вы хотите показать.

Σ_{d} T I M E [n^{2}]

$\Sigma_d TIME[n^2]$

d

$d$

Райан Уильямс

Ответ на пересмотренный вопрос (пересмотр 4 вопроса) - нет. Если задача решения L разрешима за время O ( n ^k ) с помощью машины P _i P, то L может быть решена за линейное время машиной Тьюринга с оракулом для L , который является машиной ∑ _{i +1} P. Следовательно, TIM _i TIME [O ( n ^k )] ⊆ Σ _{i +1} TIME [O ( n )].

Цуёси Ито
источник

Σ_{j} T I M E [t (n)]

$\Sigma_j TIME[t(n)]$

Σ_{j} T I M E [O (n^{k})] \subseteq Σ_{j + 1} T I M E [O (n)]

$\Sigma_j TIME[O(n^k)] \subseteq \Sigma_{j+1} TIME[O(n)]$

j, k

$j,k$

N P \neq c o N P

$NP \neq coNP$

N P = c o N P

$NP = coNP$

Σ_{j} T I M E [O (n^{k})] \subseteq Σ_{j + 1} T I M E [O (n)]

$\Sigma_j TIME[O(n^k)] \subseteq \Sigma_{j+1} TIME[O(n)]$

j, k

$j,k$

O (n^{c})

$O(n^c)$

N T I M E [O (n^{c^{2}})] \subseteq Σ_{2} T I M E [O (n)] \subseteq N T I M E [O (n^{c})]

$NTIME[O(n^{c^2})] \subseteq \Sigma_{2} TIME[O(n)] \subseteq NTIME[O(n^{c})]$

@Ryan: Я использовал следующее определение: L∈ΣiTIME [t (n)], если существует язык O∈Σ (i − 1) P и недетерминированная машина Тьюринга времени t (n) с оракулом для O, который распознает Л. Я думал, что это стандартное определение, но у меня нет никаких ссылок, чтобы подтвердить мою претензию. Какое определение вы используете?

Tsuyoshi Ito

Определение таково:

L \in Σ_{i} T I M E [t (n)]

$L \in \Sigma_i TIME[t(n)]$ если есть линейный предикат времени

R (x, y_{1}, \dots, y_{i})

$R(x,y_1,\ldots,y_i)$ такой, что

x \in L ⟺ (\exists y_{1} : | y_{1} | \leq t (| x |)) \dots (\forall y_{i} : | y_{i} | \leq t (| x |)) R (x, y_{1}, \dots, y_{i})

$x \in L \iff (\exists y_1 : |y_1|\leq t(|x|))\cdots (\forall y_i : |y_i| \leq t(|x|))R(x,y_1,\ldots,y_i)$ правда.

Райан Уильямс

@ Райан: Хорошо, я не знал это определение. Если это то, что хотел спросить спрашивающий, мой ответ не применяется.

Цуёси Ито