Apakah

Dalam "paragraf terakhir" dari "halaman pertama" dari makalah berikut:

Vikraman Arvind , Johannes Köbler , Uwe Schöning , Rainer Schuler , "Jika NP Memiliki Sirkuit Ukuran Polinomial, maka MA = AM," Ilmu Komputer Teoretis, 1995.

Saya menemukan klaim yang agak kontra-intuitif:

$(\Sigma^P_2 \cap \Pi^P_2)^{NP} = \Sigma^P_3 \cap \Pi^P_3$

Saya pikir identitas di atas disimpulkan dari yang berikut:

$(\Sigma^P_2)^{NP} = \Sigma^P_3$

dan

$(\Pi^P_2)^{NP} = \Pi^P_3$

Yang pertama lebih sederhana ditulis sebagai , yang cukup aneh!$(NP^{NP})^{NP} = NP^{NP^{NP}}$

Sunting: Sehubungan dengan komentar Kristoffer di bawah ini, saya ingin menambahkan komentar inspiratif berikut dari buku kompleksitas Goldreich (hlm. 118-119):

Harus jelas bahwa kelas dapat didefinisikan untuk dua kelas kompleksitas C 1 dan C 2 , asalkan C 1 dikaitkan dengan kelas mesin standar yang menggeneralisasi secara alami ke kelas mesin oracle. Sebenarnya, kelas C C 2 1 tidak didefinisikan berdasarkan kelas C 1 melainkan dengan analogi itu. Secara khusus, misalkan C $C_1^{C_2}$$C_1$$C_2$$C_1$$C_1^{C_2}$$C_1$$C_1$adalah kelas set yang dapat dikenali (atau lebih tepatnya diterima) oleh mesin dari jenis tertentu (misalnya, deterministik atau non-deterministik) dengan batas sumber daya tertentu (misalnya, batas waktu dan / atau batas ruang). Kemudian, kami mempertimbangkan mesin oracle analog (yaitu, dari jenis yang sama dan dengan batas sumber daya yang sama), dan mengatakan bahwa jika ada mesin oracle yang memadai M 1 (yaitu, dari jenis ini dan batas sumber daya) dan set S 2 ∈ C 2 sehingga M S 2 1 menerima set S .$S \in C_1^{C_2}$$M_1$$S_2 \in C_2$$M_1^{S_2}$$S$

adalah sekumpulan bahasa yang diputuskan oleh mesin turing bergantian dalam eksistensial, dan kemudian keadaan universal, dengan oracle dalam NP. Baik bagian universal dan eksistensial dapat meminta NP.${\Sigma_2^P}^{NP}$

Oleh karena itu, dalam hal ini Anda memutuskan untuk menulis ini sebagai maka cara Anda harus memikirkannya adalah sebagai ( N P N P A ∪ A ) (dengan ∪ maksud saya oracle baik untuk A atau ke N P A bahasa).$(NP^{NP})^{A}$$(NP^{NP^A\cup A})$$\cup$$A$$NP^A$

Karenanya sama dengan ( N P ( N P N P ) ) N P yang tentunya sama dengan ( N P N P N P ) karena setiap kueri yang dapat Anda buat ke oracle N P , Anda dapat membuatnya ke N P N P oracle.${\Sigma_2^P}^{NP}$$(NP^{(NP^{NP})})^{NP}$$(NP^{NP^{NP}})$$NP$$NP^{NP}$

From Arora and Barak (p. 102) theorem 5.12: "For every $i\geq 2$, $\sum_i^p=NP^{\sum_{i-1}SAT}$". Remember that $\sum_{i}SAT$ is the QBF formula with $i$ alternations which is complete for $\sum_i^p$. Then $\sum_2^p=NP^{SAT}$ and given that SAT is NP-complete you just write $\sum_2^p=NP^{NP}$, so far so good. Extending this notation to $i=3$ you get $NP^{NP^{NP}}$, but the last two "NPs" are just an oracle for the language $\sum_{2}SAT$ with at most 2 alternations. It seems to me that its just a shorthand notation for oracle access.