Czy upadek

Zawarte w między każdym poziomie hierarchii wielomianowej złożoności są różne klasy, w tym , , oraz . Z powodu braku lepszej terminologii będę odwoływał się do tych i innych klas pośrednich między poziomami i w hierarchii wielomianowej. Dla celów tego pytania, załóżmy, że są to klasy zawarte w $\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}$ ale zawierają i / lub . Chcemy unikać włączenia , jeśli to możliwe, ponieważ jest to trywialnie równoważne jeśli spadnie do poziomu . $\Sigma_i^\text{P}$ $\Pi_i^\text{P}$ $\Sigma_{i+1}^\text{P} \cap \Pi_{i+1}^\text{P}$ $\text{PH}$ ${i+1}^{th}$

Ponadto zdefiniuj następujące elementy:
$\text{DP}_i = \left \{ L \cap L' : L \in \Sigma_i^\text{P} \text{ and } L' \in \Pi_i^{\text{P}} \right \}$

Powyżej jest uogólnieniem klasy (również napisanej ). W tej definicji jest równoważne . Jest to rozważane w innym pytaniu dotyczącym cstheory.se . Łatwo zauważyć, że zawiera zarówno i . $\text{DP}$ $\text{D}^\text{P}$ $\text{DP}$ $\text{DP}_1$ $\text{DP}_i \subseteq \Delta_{i+1}^{\text{P}}$ $\Sigma_i^\text{P}$ $\Pi_i^\text{P}$

Schemat referencyjny:

Schemat PH

Pytanie:
Załóżmy, że hierarchia wielomianowa zwija się do poziomu , ale nie zapada się do poziomu . Oznacza to, że i . ${i+1}^{th}$ $i^{th}$ $\Sigma_{i+1}^\text{P}=\Pi_{i+1}^\text{P}$ $\Sigma_{i}^\text{P}\neq\Pi_{i}^\text{P}$

Czy możemy powiedzieć coś więcej na temat związków między tymi klasami pośrednimi a innymi na dowolnym poziomie poniżej ? Czy istnieje schemat dla kolekcji klas złożoności, w którym dla każdej kolekcji klasy są równoważne tylko wtedy, gdy spadnie dokładnie do dowolnie wybranego poziomu? $i+1$ $\text{PH}$

Podobnie jak obserwacji, załóżmy, że w hierarchii zwinięte do konkretnej jednej z tych klas pośrednich (takich jak ). W zależności od wybranej klasy, czy wiemy, czy to załamanie musi nadal rozciągać się w dół, być może nawet do poziomu ? $\Delta_{i+1}^{\text{P}}$ $i^{th}$

Na powyższe pytanie częściowo zbadano i na które odpowiedzi udzielił Hemaspaandra i in. al:
Upadek w dół w hierarchii wielomianowej
Czy ktoś zdaje sobie sprawę z dodatkowych przykładów niewymienionych w tym artykule lub ma dalszą intuicję co do tego, co musi się stać, aby klasa mogła to osiągnąć?

cc.complexity-theory polynomial-hierarchy mdxn
źródło

Odpowiedzi:

Nie mam dobrej odpowiedzi, ale w duchu złożoności mam kilka odpowiedzi, które sugerują, że trudno jest znaleźć dobrą odpowiedź :).

$\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$
Ker-I Ko podaje wyrocznie, w których oddziela poziomy od poziomów . Gdy te dwie hierarchie się ze sobą przeplatają, daje to przynajmniej trochę informacji o relatywnych załamaniach problemów między poziomami . $\mathsf{BPH}$ $\mathsf{PH}$ $\mathsf{PH}$
To następne odniesienie jest złym kierunkiem, ale możesz być również zainteresowany wynikiem i jego technikami. Chang i Kadin pokazali, że jeśli hierarchia logiczna (która żyje całkowicie poniżej drugiego poziomu , ale rozciąga do całej hierarchii) załamie się do swojego poziomu, wówczas upadnie do poziomu hierarchii logicznej nad . $\mathsf{PH}$ $\mathsf{DP}$ $k$ $\mathsf{PH}$ $k$ $\mathsf{\Sigma_2 P}$

Joshua Grochow
źródło

Czy be

Σ_{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}?$

T ....

przepraszam, ale pomyślałem poprawny? Np .:

Σ_{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$

T ....