Mengapa P = NP tidak menyiratkan P = AP (yaitu P = PSPACE)?

Diketahui bahwa jika maka hierarki polinomial runtuh dan .$\mathbf{P}=\mathbf{NP}$$\mathbf{P}=\mathbf{PH}$

Ini dapat dengan mudah dipahami secara induktif menggunakan mesin oracle. Pertanyaannya adalah - mengapa kita tidak dapat melanjutkan proses induktif di luar tingkat pergantian yang konstan dan membuktikan (alias )?$\mathbf{P}=\mathbf{AltTime}(n^{O(1)})$$\mathbf{AP}=\mathbf{PSPACE}$

Saya mencari jawaban yang intuitif.

Dalilnya ( = P H ) adalah induksi menggunakan P = N P . Induksi menunjukkan bahwa untuk bilangan asli k , P = A l t T i m e ( k ) (dan A l t T i m e ( O ( 1 ) $\mathbf{P}=\mathbf{AltTime}(O(1))$$=\mathbf{PH}$$\mathbf{P}=\mathbf{NP}$ $k$$\mathbf{P}=\mathbf{AltTime}(k)$$\mathbf{AltTime}(O(1))$ hanya persatuan mereka).

Induksi tidak bekerja ketika jumlah pergantian dapat berubah dengan ukuran input (yaitu ketika jumlah pergantian yang mungkin dari mesin bukan angka tetapi fungsi dari ukuran input, yaitu kita tidak menunjukkan bahwa eksekusi mesin pada satu input dapat dikurangi menjadi tidak ada alternatif, kami menunjukkan bahwa eksekusi mesin pada semua input dapat "seragam" dikurangi menjadi tidak ada alternatif).

Mari kita lihat pernyataan yang serupa tetapi lebih sederhana. Kami ingin menunjukkan bahwa fungsi identitas akhirnya mendominasi semua fungsi konstan ( f ≪ g iff untuk semua kecuali banyak n f ( n ) ≤ g ( n ) ). Itu bisa dibuktikan dengan induksi. Untuk semua k , k ≪ n (yaitu f k ≪ i d di mana f k ( n ) = $id(n)=n$$f \ll g$$n$ $f(n) \leq g(n)$$k$$k \ll n$$f_k \ll id$$f_k(n)=k$), tetapi kami tidak memiliki ini untuk fungsi yang tidak konstan seperti , n 2 ≪ ̸ n .$n^2$$n^2 \not \ll n$

Bandingkan hierarki polinomial dengan hierarki untuk bukti interaktif. Jika untuk beberapa k tetap , Anda memiliki k alternatif dalam bukti interaktif - IP ( k ) - kelas kompleksitas yang dihasilkan tidak memiliki kekuatan lebih dari apa yang Anda dapatkan dengan dua alternatif - yaitu, IP ( k ) = IP (2 ) = AM (dengan asumsi k ≥2). Namun, jika Anda mengizinkan jumlah polinomial dari pergantian, Anda mendapatkan kelas kompleksitas IP = PSPACE, yang diyakini jauh lebih besar dari AM, kelas terkandung dalam Π ₂ P, pada tingkat kedua hirarki polinomial. Jadi fenomena ini benar-benar terjadi (walaupun, tidak sejauh yang kita tahu, dengan hierarki polinomial).

Ini terjadi karena pengurangan yang mengambil masalah ukuran n di IP ( k ) dan mengubahnya menjadi masalah di IP (2) meledakkan ukuran masalah, sehingga sementara untuk setiap IP tertentu ( k ) masalahnya tetap polinomial-size , jika Anda membiarkan k bervariasi, reduksi yang dihasilkan tidak memberikan masalah yang polinomial dalam k .

Berikut adalah sedikit intuisi mengenai kesenjangan antara pergantian konstan dan tidak terikat: operasi polinomial yang diulang beberapa kali adalah polinomial, tetapi diulang beberapa kali polinomial bisa eksponensial. Misalnya, lakukan penggandaan berulang pada dirinya sendiri:

v = 2
for(i=1 to n)
  v = v*v

Jumlah iterasi linier, dan output eksponensial. Tetapi jika Anda memperbaiki n, itu jumlahnya banyak pada ukuran nilai awal.

Di bawah ini saya memperluas sedikit pada titik dalam jawaban Peter dengan mencoba melakukan penghapusan kuantifikasi untuk lebih dari jumlah langkah yang konstan untuk melihat di mana ia gagal dan jika ada yang bisa diselamatkan dari upaya seperti itu.

Mari kita coba untuk memperkuat $\mathsf{P}=\mathsf{NP}$ untuk lebih dari jumlah kali konstan.

Asumsikan bahwa $\mathsf{P}=\mathsf{NP}$ . Oleh karena itu ada mesin waktu polinomial yang memecahkan Ext-Circuit-SAT (adakah ekstensi yang memuaskan untuk rangkaian yang diberikan dan penugasan sebagian untuk inputnya?).

Lebih formal, kami memiliki algoritma polytime $A$ dengan polinomial running time $p(n)\in\rm{poly}(n)$ st

Diberikan sirkuit Boolean $\varphi$ , dan penugasan sebagian $\tau$ ke input,
$A$ mengembalikan "ya" jika ada ekstensi $\tau$ yang memenuhi $\varphi$ , dan mengembalikan "tidak" sebaliknya.

Untuk melewati waktu yang konstan, kita perlu melakukan penghapusan quantifier secara efektif. Kita bisa melakukan ini karena Masak-Levin Teorema adalah teorema yang konstruktif, sebenarnya itu memberikan waktu polinomial algoritma $Cook$ st

Mengingat DTM $M$ menerima dua input, dan tiga angka unary $n$ , $m$ , dan $t$ ,
$Cook(M, n, m, t)$ mengembalikan sirkuit Boolean ukuran $O(t^2)$ yang mensimulasikan $M$ masukan panjang $(n,m)$ untuk $t$ langkah.

Mari kita coba gunakan ini untuk memperluas argumen untuk $\mathsf{P}=\mathsf{PH}$ untuk mendapatkan algoritma penyelesaian TQBF (sebenarnya TQBCircuit, yaitu masalah Sirkuit Boolean Totally Quantified).

Ide dari algoritma ini adalah sebagai berikut: kita berulang kali menggunakan $Cook$ pada $A$ untuk menghapus bilangan dari rangkaian diukur diberikan. Ada sejumlah linear dari bilangan jadi kami berharap untuk mendapatkan algoritma waktu polinomial (kami memiliki algoritma dengan polynomially banyak langkah menggunakan polinomial waktu subroutine $Cook$ ). Pada akhir proses ini pembilang eliminasi kita akan memiliki sirkuit quantifier bebas yang dapat dievaluasi dalam waktu polinomial (Circuit Nilai masalah adalah di $\mathsf{P}$ , biarkan $CV$ menjadi algoritma waktu polinomial untuk menghitung nilai rangkaian sirkuit yang diberikan) .

Namun kita akan melihat bahwa gagasan ini tidak berhasil (karena alasan yang sama ditunjukkan oleh Peter).

• Misalkan $\varphi$ menjadi sirkuit terkuantifikasi, (diinisialisasi ke rumus terkuantifikasi yang diberikan).
• Biarkan $k$ jumlah pengukur dalam $\varphi$ .

• Untuk $i$ dari $k$ ke $1$ lakukan

  • Mari $\psi$ = $Qx_k \sigma(x_1,...,x_k)$ menjadi quantifier terakhir dan bagian quantifier bebas.

  • Jika $Q = "\exists"$ ,

    1. Hitung $C = Cook(A, |\sigma|, |x_1|+...+|x_k-1|, p)$ ,
    2. Mengganti bit input dengan $\sigma$ di sirkuit $C$ ,
    3. Ganti $\psi$ dengan $C$ dalam $\varphi$ .

  • Jika $Q = "\forall"$ ,

    1. Pertimbangkan $\psi$ sebagai $\lnot \exists x_k \lnot \sigma$ ,
    2. Hitung $C = Cook(A, |\lnot \sigma|, |x_1|+...+|x_k-1|, p)$ ,
    3. Mengganti bit input dengan $\lnot \sigma$ di sirkuit $C$ ,
    4. Ganti $\psi$ dengan $\lnot C$ di $\varphi$ .
• Hitung dan kembalikan $CV(\varphi)$ .

Algoritma yang dihasilkan terlihat waktu polinomial: kami memiliki banyak langkah polinomial, setiap langkah dihitung waktu polinomialnya. Namun ini tidak benar, algoritma ini bukan waktu polinomial.

Menggunakan waktu polinomial subrutin dalam algoritma waktu polinomial adalah waktu polinomial. Masalahnya adalah bahwa secara umum ini tidak perlu benar jika nilai-nilai yang dikembalikan oleh subrutin tidak dari ukuran polinomial dalam input asli dan kami menganggap bahwa kami melakukan penugasan tentang nilai-nilai yang kembali dari subrutin. (Dalam model TM kita harus membaca output dari setiap polinomial sedikit waktu subrutin demi sedikit.) Berikut ukuran nilai kembali dari algoritma $Cook$ yaitu meningkatkan (dapat menjadi kekuatan dari ukuran masukan yang diberikan untuk itu , daya yang tepat tergantung pada waktu menjalankan $A$ dan sekitar $p^2(|input|)$, jadi karena kita tahu bahwa $A$ tidak boleh kurang dari waktu linier, $|output|$setidaknya $|input|^2$ ).

Masalahnya mirip dengan kode sederhana di bawah ini:

• Diberikan $x$ ,
• Biarkan $n = |x|$,
• Biarkan $y = x$ ,
• Untuk $i$ dari $1$ sampai $n$ lakukan
  • Biarkan $y = y^{|y|}$, (yaitu gabungan dari $|y|$ salinan $y$ )
• Kembali y

Setiap kali kita mengeksekusi $y = y^{|y|}$kami menguadratkan ukuran $y$ . Setelah eksekusi $n$ kita akan memiliki $y$ yang $x^{2^n}$ dan memiliki ukuran $n2^n$ , jelas bukan polinomial dalam ukuran input.

Mari kita asumsikan bahwa kita hanya mempertimbangkan rumus terkuantisasi dengan $k(n)$ alternatif kuantifikasi (di mana $n$ adalah ukuran total dari rumus terkuantifikasi).

Asumsikan bahwa $A$ berjalan dalam waktu $p$ (misalnya linear waktu yang tidak dikesampingkan begitu jauh), dan memiliki mungkin lebih efisien $Cook$ algoritma keluaran sirkuit yang lebih kecil dari ukuran $l(t)$ di tempat $t^2$ , maka kita mendapatkan sebuah algoritma untuk ExtCircuitSat yang berjalan dalam waktu $(l\circ p)^{O(k)}(n)=\underbrace{l(p(l(p(\dots(l(p(n)))))))}_{O(k)\mbox{ compositions}}$ . Bahkan dalam kasus yang kedua$l$dan$p$adalah linier (tapi dengan jumlah koefisien$a\geq 2$) kita akan mendapatkan sebuah algoritma yang berjalan dalam waktu$\Omega(n2^{k(n)})$dan jika$k(n) = \Theta(n)$itu akan menjadi$\Omega(n2^n)$ mirip dengan algoritma brute-force (dan bahkan ini didasarkan pada asumsi Cook-Levin dapat dilakukan pada algoritma yang menghasilkan sirkuit ukuran linier dalam waktu berjalan dari algoritma).

Saya pikir ini karena pada setiap level PH, jumlah pergantian adalah konstan (yaitu independen dari ukuran input), sementara di AP, jumlah pergantian dapat tidak terikat (namun jumlahnya banyak dalam ukuran input).