Masalah interepretasi sederhana mengenai Hirarki Polinomial?

Begitu $NP$ singkatan dari masalah di mana kita memiliki saksi kecil yang dapat diverifikasi $YES$ contoh dan $coNP$ untuk saksi kecil yang dapat diverifikasi $NO$contoh. Bagaimana cara kerjanya?

1. $P^{NP}$

2. $NP^{NP}$

3. $coNP^{NP}$

4. dan seterusnya?

Ada interpretasi logis dari berbagai tingkatan hirarki polinom, yang memperluas karakterisasi saksi $\mathsf{NP}$ dan $\mathsf{coNP}$.

Sebuah bahasa $L$ ada di $\Sigma_k^P$ jika ada predikat polytime $f$ dan polinomial $\ell$ seperti yang

• $\exists |y| \le \ell(|x|)$ berarti ada nomor $y$ yang panjangnya paling banyak $\ell(|x|)$ seperti yang ...
• $\forall |y| \le \ell(|x|)$ berarti untuk semua $y$ yang panjangnya paling banyak $\ell(|x|)$, yang berikut ini berlaku ...
• $Q$ adalah $\exists$ jika $k$ aneh dan $\forall$ jika $k$ bahkan.

Demikian pula, $L$ ada di $\Pi_k^P$ jika dapat ditulis dengan cara yang sama, hanya dimulai dengan $\forall$.

Sebagai contoh, $\mathsf{NP}^{\mathsf{NP}}$ adalah $\Sigma_2^P$, dan terdiri dari semua bahasa sedemikian rupa sehingga

Contoh ketiga Anda adalah $\mathsf{P}^{\mathsf{NP}}$, yang mana $\Delta_2^P$. Saya tidak yakin apa karakterisasi logisnya.

Untuk mengatakan $\mathsf{NP}$mengandung masalah dengan "saksi kecil yang dapat diverifikasi" secara konseptual paling tidak akurat. Para saksi hanya dibatasi secara polinomi karena kami ingin verifikasi menjadi efisien (yaitu, berjalan dalam waktu polinomial). Dalam situasi seperti itu, hanya awalan polinomial panjang dari saksi mana saja yang relevan, maka dari itu mengapa kami menuntut saksi polinomial panjang. Juga, "kecil" berpotensi berarti konstan atau logaritmik; mereka tidak digunakan, tentu saja, karena mereka dapat dipaksa oleh algoritma waktu polinomial (dan hanya memberi kita masalah dalam$\mathsf{P}$).

Cara gagasan sistem buktinya $\mathsf{NP}$generalisasi untuk menghasilkan hierarki polinom mirip dengan sudut pandang logis yang dijelaskan Yuval Filmus dalam jawabannya. Izinkan saya memperkenalkan pandangan yang kurang teknis di baliknya.

Kami mempertimbangkan game dua pihak yang didasarkan pada QBF. Sebuah instance (atau "papan" jika Anda ingin membayangkannya sebagai permainan papan seperti catur atau catur) dari permainan seperti itu adalah formula$\varphi(x_1, y_1, \ldots, x_m, y_m)$, dan dua pemain, katakanlah $A$ dan $B$, bergiliran memilih nilai untuk $x_i$ dan $y_i$masing-masing. Setiap pilihan tersebut merupakan langkah . Ketika tidak ada lagi nilai yang tersisa, rumus (yaitu, posisi akhir gim) dievaluasi;$A$ menang jika itu benar, dan $B$ menang jika itu salah.

Game ini memodelkan penjumlahan eksistensial dan universal dengan cara berikut: Jika rumusnya adalah QBF sejati, maka $A$ (yang memainkan peran quantifiers eksistensial) akan selalu memiliki strategi kemenangan dan dapat memilih serangkaian $x_1, \ldots, x_m$ yang menyebabkan $\varphi$ benar terlepas dari nilai-nilai $y_1, \ldots, y_m$ dipilih oleh $B$(yang memainkan peran quantifiers universal). Contoh "ya" adalah contoh di mana QBF benar, yaitu,$A$ selalu memiliki strategi kemenangan, apa pun caranya $B$ memainkan.

$\Sigma_i$ dan $\Pi_i$ kemudian sesuai dengan game yang berlangsung selama $i$ bergerak dan di mana $A$ dan $B$, masing-masing, pergi dulu. Sebenarnya, Anda bahkan mendapatkannya$\textsf{PSPACE}$ dan $\textsf{PH} \subseteq \textsf{PSPACE}$ dimasukkan sebagai bonus karena sesuai dengan kelas permainan yang berlangsung untuk jumlah gerakan yang sewenang-wenang (meskipun telah ditentukan sebelumnya).

Perhatikan juga itu $\Sigma_1 = \mathsf{NP}$ dan $\Pi_1 = \mathsf{coNP}$ adalah kasus yang agak merosot dari game ini karena $B$ dan $A$, masing-masing, tidak mendapatkan kesempatan untuk bergerak sama sekali! Misalnya, untuk contoh "ya" dari$\Pi_1 = \mathsf{coNP}$, $A$ dapat menang hanya dengan tidak melakukan apa-apa (karena contoh "ya" adalah tautologi dan benar terlepas dari apa $B$ memilih).

Ada juga versi yang lebih umum dari yang di atas yang didasarkan pada permainan generik (dan bukan QBF secara khusus). Anda dapat menemukannya, misalnya, di bagian 5.4 "PSPACE and Games" dari Goldreich's "Computational Complexity: A Conceptual Perspective" (di sini ada tautan gratis ke versi konsep; lihat hlm. 174 serta hlm. 118–121) .

$\mathsf{P}^{\mathsf{NP}}$ adalah penutupan $\mathsf{NP}$dalam waktu polinomial Pengurangan turing (= Pengurangan masak). Oleh karena itu, ditutup di bawah pengurangan Cook, sehingga kami miliki$\mathsf{P}^{\mathsf{NP}}=\mathsf{P}^{\mathsf{P}^{\mathsf{NP}}}$. Bahkan, untuk oracle apa pun$\mathsf{A}$, kami mendefinisikan $\mathsf{P}^{\mathsf{A}}$ sebagai penutupan $\mathsf{A}$ di bawah pengurangan Cook, dan kami selalu punya $\mathsf{P}^{\mathsf{A}}=\mathsf{P}^{\mathsf{P}^{\mathsf{A}}}$ dan $\mathsf{NP}^{\mathsf{A}}=\mathsf{NP}^{\mathsf{P}^{\mathsf{A}}}$. Juga $\mathsf{coNP}^{\mathsf{A}}=\mathsf{coNP}^{\mathsf{P}^{\mathsf{A}}}$ dan $\mathsf{P}^{\mathsf{NP}}=\mathsf{P}^{\mathsf{coNP}}$. Tetapi pengurangan Cook terasa sedikit tidak wajar untuk masalah keputusan.

Catat itu $\mathsf{P}$ adalah kelas fungsi disguide, dan itu $\mathsf{P}^{\mathsf{NP}}$juga kelas fungsi yang menyamar. Mari kita menulis$\mathsf{PF}$ untuk kelas fungsi parsial waktu komputasi polinomial, yaitu kelas fungsi yang sesuai dengan $\mathsf{P}$, dan $\mathsf{PF}^{\mathsf{NP}}$ untuk kelas fungsi yang berkaitan dengan $\mathsf{P}^{\mathsf{NP}}$. Termasuk fungsi parsial memungkinkan untuk menggunakan notasi yang mapan (digunakan dalam A taksonomi kompleksitas kelas fungsi oleh A. Selman, 1994) yang menghindari nama bentrok dengan kelas yang tidak terkait$\mathsf{FP}$.

Reduksi masak terasa lebih alami untuk kelas fungsi. Anda mungkin mengalami pengurangan Cook (dan secara implisit juga kelasnya$\mathsf{PF}^{\mathsf{NP}}$) pada titik di mana buku teks atau profesor Anda menjelaskan mengapa tidak masalah untuk hanya melihat masalah keputusan. Biasanya, sesuatu seperti algoritma (dari$\mathsf{PF}^{\mathsf{NP}}$) untuk menghitung penugasan memuaskan terakhir secara leksikografis dari instance SAT yang diberikan diuraikan. Yang pertama bertanya kepada oracle apakah ada tugas yang memuaskan sama sekali, dan kemudian menentukan nilai-nilai variabel (biner)$x_k$ dengan berturut-turut bertanya kepada oracle apakah ada tugas yang memuaskan di mana $x_1,\dots,x_{k-1}$ diatur ke nilai yang sudah ditentukan, dan $x_k$ diatur ke $1$. Jika ya, maka satu set$x_k$ untuk $1$, jika tidak, satu set $x_k$ untuk $0$. (Perhatikan bahwa ini adalah fungsi parsial, karena fungsi tersebut tidak terdefinisi jika tidak ada penugasan yang memuaskan.)

Biarkan saya mencoba untuk mengatakan beberapa kata tentang pernyataan Yuval Filmus:

Contoh ketiga Anda adalah $\mathsf{P}^{\mathsf{NP}}$, yang mana $\Delta_2^P$. Saya tidak yakin apa karakterisasi logisnya.

Ada dua kesulitan untuk diatasi: (1) karakterisasi kelas fungsi memiliki rasa yang berbeda dari karakterisasi logis dari kelas keputusan, dan (2) setidaknya untuk $\mathsf{P}^{\mathsf{A}}$kita harus memodelkan karakter deterministik dari pertanyaan ke oracle$\mathsf{A}$.

Jika kita melihat kelasnya $\mathsf{UPF}$ fungsi parsial sesuai dengan kelas $\mathsf{UP}$ masalah keputusan pertama, maka kita dapat mengabaikan (2) sejenak: Fungsi parsial $pf$ ada di $\mathsf{UPF}^{\Sigma_k^P}$ jika ada fungsi parsial polytime $p$, predikat polytime $f$ dan polinomial $\ell$ seperti yang $pf(x)=p(x,z)$ dimana

• $\exists |y| \le \ell(|x|)$ berarti ada nomor $y$ yang panjangnya paling banyak $\ell(|x|)$ seperti yang ...
• $\forall |y| \le \ell(|x|)$ berarti untuk semua $y$ yang panjangnya paling banyak $\ell(|x|)$, yang berikut ini berlaku ...
• $Q$ adalah $\exists$ jika $k$ aneh dan $\forall$ jika $k$ bahkan.

Seseorang dapat mencoba mengatasi (2) dengan memperkenalkan operator $\operatorname{BIT}(z,i):=z[i]$ dan $\operatorname{TRUNC}(z,i):=z\left|_{[1,i)}\right.$. Tapi itu masih akan menjadi jelek, dan orang bisa berargumen apakah ini benar-benar merupakan karakterisasi logis.