Известно ли, что распад

Содержится в-между каждым уровнем многочлена иерархии различные классы сложности, в том числе $\Delta_i^{\text{P}}$ , $\text{DP}$ , $\text{BH}_k$ , и $\Sigma_i^\text{P} \cap \Pi_i^\text{P}$ . Из-за отсутствия лучшей терминологии я буду ссылаться на эти и любые другие как промежуточные классы между уровнями $i$ и $i+1$ в иерархии полиномов. Для целей этого вопроса, предполагают , что они являются классы , содержащиеся в $\Sigma_{i+1}^\text{P} \cap \Pi_{i+1}^\text{P}$ но содержат $\Sigma_i^\text{P}$ и / или $\Pi_i^\text{P}$ . Мы хотим , чтобы избежать включения $\Sigma_{i+1}^\text{P} \cap \Pi_{i+1}^\text{P}$ , если это возможно, так как это тривиально эквивалентно $\text{PH}$ , если он падает на ${i+1}^{th}$ уровень.

Кроме того, определить следующее:
$\text{DP}_i = \left \{ L \cap L' : L \in \Sigma_i^\text{P} \text{ and } L' \in \Pi_i^{\text{P}} \right \}$

Выше приведено обобщение класса $\text{DP}$ (также пишется $\text{D}^\text{P}$ ). В этом определении $\text{DP}$ эквивалентен $\text{DP}_1$ . Это рассматривается в другом вопросе cstheory.se . Легко видеть , что $\text{DP}_i \subseteq \Delta_{i+1}^{\text{P}}$ и содержит как $\Sigma_i^\text{P}$ и $\Pi_i^\text{P}$ .

Справочная схема:

Диаграмма PH

Вопрос:
Предположим, что полиномиальная иерархия коллапсирует до уровня , но не коллапсирует до уровня . То есть, и . ${i+1}^{th}$ $i^{th}$ $\Sigma_{i+1}^\text{P}=\Pi_{i+1}^\text{P}$ $\Sigma_{i}^\text{P}\neq\Pi_{i}^\text{P}$

Можем ли мы сказать что-нибудь еще об отношениях между самими этими промежуточными классами и другими на любом уровне ниже ? Существует ли схема для коллекции классов сложности, где для каждой коллекции классы эквивалентны тогда и только тогда, когда рухнет точно до произвольно выбранного уровня? $i+1$ $\text{PH}$

Подобно тому , как катамнестическая, предположит , что иерархия разрушилась каким - либо конкретные одной из этих промежуточных классов (например, ). В зависимости от класса выбранного мы знаем , если этот коллапс должен продолжать оказывать вниз, возможно , даже до уровень? $\Delta_{i+1}^{\text{P}}$ $i^{th}$

Вышеуказанный вопрос был частично исследован и получен ответ в статье Hemaspaandra et. al:
Нисходящий коллапс в полиномиальной иерархии
Кто-то случайно узнал о дополнительных примерах, не упомянутых в этой статье, или у него есть дополнительное понимание того, что должно произойти, чтобы класс выполнил это?

cc.complexity-theory polynomial-hierarchy mdxn
источник

Ответы:

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

Обратите внимание , что обобщенный вариант теоремы Ладнера подразумевает , что существует бесконечно много поли время градусов строго в между и любой степенью поли времени строго над ним. В частности, если иерархия падает на -го уровня , но не -м, то существует бесконечное множество р-градусов между и . $\mathsf{\Sigma_i P}$ $i+1$ $i$ $\mathsf{\Sigma_i P}$ $\mathsf{\Sigma_{i+1} P} \cap \mathsf{\Pi_{i+1} P}=\mathsf{\Sigma_{i+1} P}$
Если я правильно помню, построение оракула, для которого выглядит как арифметическая иерархия, все еще остается открытой проблемой. Под «выглядит как арифметическая иерархия» я имею в виду, что не коллапсирует, и для всех . По крайней мере, это говорит о том, что ответ на ваш вопрос может быть неизвестен. $\mathsf{PH}$ $\mathsf{PH}$ $\mathsf{\Sigma_{k} P} \cup \mathsf{\Pi_k P} \subsetneq \mathsf{\Delta_{k+1} P} = \mathsf{\Sigma_{k+1} P} \cap \mathsf{\Pi_{k+1} P}$ $k$
$\mathsf{BPH}$ $\mathsf{PH}$ $\mathsf{PH}$
$\mathsf{PH}$ $\mathsf{DP}$ $k$ $\mathsf{PH}$ $k$ $\mathsf{\Sigma_2 P}$

Джошуа Грохов
источник

Σ_{k} P \cup Π_{k} P ⊊ Δ_{k} P = Σ_{k + 1} P \cap Π_{k + 1} P

$\mathsf{\Sigma_{k} P} \cup \mathsf{\Pi_k P} \subsetneq \mathsf{\Delta_k P} = \mathsf{\Sigma_{k+1} P} \cap \mathsf{\Pi_{k+1} P}$

Δ_{k} P = Σ_{k} P \cup Π_{k} P ⊊ Δ_{k + 1} P = Σ_{k + 1} P \cap Π_{k + 1} P ?

$\mathsf{\Delta_{k} P}=\mathsf{\Sigma_{k} P} \cup \mathsf{\Pi_k P} \subsetneq \mathsf{\Delta_{k+1} P} = \mathsf{\Sigma_{k+1} P} \cap \mathsf{\Pi_{k+1} P}?$

Σ_{k - 1}^{P} \cup Π_{k - 1}^{P} \subseteq Δ_{k}^{P} \subseteq Σ_{k}^{p} \cap Π_{k}^{P} \subseteq Σ_{k}^{P} \cup Π_{k}^{P}

$\Sigma_{k-1}^P\cup\Pi_{k-1}^P\subseteq \Delta_k^P\subseteq \Sigma_k^p\cap\Pi_k^P\subseteq \Sigma_k^P\cup\Pi_k^P$

P = Σ_{0}^{P} \cup Π_{0}^{P} = P \cup P \subseteq Δ_{1}^{P} = P \subseteq Σ_{1}^{p} \cap Π_{1}^{P} = N P \cap c o N P \subseteq Σ_{1}^{P} \cup Π_{1}^{P} = N P \cup c o N P \subseteq Δ_{2}^{P} = P^{N P} \subseteq Σ_{2}^{P} \cap Π_{2}^{P} \subseteq Σ_{2}^{P} \cup Π_{2}^{P} \dots

$P=\Sigma_{0}^P\cup\Pi_{0}^P=P\cup P\subseteq \Delta_1^P=P\subseteq \Sigma_1^p\cap\Pi_1^P=NP\cap coNP\subseteq \Sigma_1^P\cup\Pi_1^P=NP\cup coNP\subseteq \Delta_2^P=P^{NP}\subseteq\Sigma_2^P\cap\Pi_2^P\subseteq\Sigma_2^P\cup\Pi_2^P\dots$