Adalah runtuhnya

Terkandung di antara setiap tingkat hirarki polinomial adalah berbagai kelas kompleksitas, termasuk $\Delta_i^{\text{P}}$ , $\text{DP}$ , $\text{BH}_k$ , dan $\Sigma_i^\text{P} \cap \Pi_i^\text{P}$ . Karena kurangnya terminologi yang lebih baik, saya akan merujuk pada ini dan yang lainnya sebagai kelas menengah antara tingkat $i$ dan $i+1$ dalam hirarki polinomial. Untuk keperluan pertanyaan ini, anggaplah mereka adalah kelas yang terkandung dalam $\Sigma_{i+1}^\text{P} \cap \Pi_{i+1}^\text{P}$ tetapi mengandung $\Sigma_i^\text{P}$ dan / atau $\Pi_i^\text{P}$ . Kami ingin menghindari menyertakan $\Sigma_{i+1}^\text{P} \cap \Pi_{i+1}^\text{P}$ , jika mungkin, karena sepele setara dengan $\text{PH}$ jika ia runtuh ke level ${i+1}^{th}$ .

Selain itu, tentukan yang berikut ini:
$\text{DP}_i = \left \{ L \cap L' : L \in \Sigma_i^\text{P} \text{ and } L' \in \Pi_i^{\text{P}} \right \}$

Di atas adalah generalisasi dari kelas $\text{DP}$ (juga ditulis $\text{D}^\text{P}$ ). Dalam definisi ini, $\text{DP}$ setara dengan $\text{DP}_1$ . Itu dipertimbangkan dalam pertanyaan cstheory.se lainnya . Sangat mudah untuk melihat bahwa $\text{DP}_i \subseteq \Delta_{i+1}^{\text{P}}$ dan berisi $\Sigma_i^\text{P}$ dan $\Pi_i^\text{P}$ .

Diagram Referensi:

Diagram PH

Pertanyaan:
Misalkan hierarki polinomial runtuh ke level , tetapi tidak runtuh ke level . Yaitu, dan . ${i+1}^{th}$ $i^{th}$ $\Sigma_{i+1}^\text{P}=\Pi_{i+1}^\text{P}$ $\Sigma_{i}^\text{P}\neq\Pi_{i}^\text{P}$

Bisakah kita mengatakan apa-apa tentang hubungan antara kelas-kelas menengah diri mereka sendiri dan orang lain dalam setiap tingkat di bawah ? Apakah ada skema untuk kumpulan kelas kompleksitas di mana, untuk setiap koleksi, kelasnya setara jika dan hanya jika runtuh persis ke tingkat yang dipilih secara sewenang-wenang? $i+1$ $\text{PH}$

Sama seperti tindak lanjut, anggaplah bahwa hierarki runtuh ke salah satu kelas menengah ini (seperti ). Tergantung pada kelas yang dipilih, kita tahu apakah keruntuhan ini harus terus memperluas ke bawah, bahkan mungkin ke tingkat? $\Delta_{i+1}^{\text{P}}$ $i^{th}$

Pertanyaan di atas sebagian dieksplorasi dan dijawab dalam sebuah makalah oleh Hemaspaandra et. al:
Runtuhnya Ke Bawah dalam Hirarki Polinomial
Apakah seseorang kebetulan mengetahui contoh tambahan yang tidak disebutkan dalam makalah ini atau memiliki intuisi lebih lanjut mengenai apa yang perlu terjadi agar suatu kelas dapat mencapai ini?

cc.complexity-theory polynomial-hierarchy mdxn
sumber

Jawaban:

Saya tidak memiliki jawaban yang baik, tetapi dalam semangat kompleksitas, saya memiliki beberapa jawaban yang menunjukkan bahwa jawaban yang baik mungkin sulit didapat :).

$\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 memberikan orakel di mana ia memisahkan level dari . Karena dua hierarki ini saling terkait satu sama lain, ini memberi Anda setidaknya beberapa informasi tentang runtuhnya masalah yang dapat relatif antara level . $\mathsf{BPH}$ $\mathsf{PH}$ $\mathsf{PH}$
Referensi berikut ini adalah arah yang salah, tetapi Anda mungkin juga tertarik dengan hasil dan tekniknya. Chang dan Kadin menunjukkan bahwa jika hierarki Boolean (yang hidup sepenuhnya di bawah level kedua , tetapi meluas ke seluruh hierarki) runtuh ke tingkat -nya maka runtuh ke tingkat - hirarki Boolean di atas . $\mathsf{PH}$ $\mathsf{DP}$ $k$ $\mathsf{PH}$ $k$ $\mathsf{\Sigma_2 P}$

Joshua Grochow
sumber

Haruskah menjadi

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

maaf tapi saya pikir benar? Misalnya:

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