Bisakah satu memperkuat P = NP di luar P = PH?

Dalam Kompleksitas Deskriptif , Immerman memiliki

Konsekuensi 7.23. Kondisi berikut ini setara:
1. P = NP.
2. Struktur yang terbatas, terurut, FO (LFP) = SO.

Ini dapat dianggap sebagai "memperkuat" P = NP untuk pernyataan yang setara atas (mungkin) kelas kompleksitas yang lebih besar. Perhatikan bahwa SO menangkap polinomial-time hierarki PH, dan FO (LFP) menangkap P, jadi ini dapat dianggap sebagai P = NP iff P = PH.

(Bagian yang menarik dari ini adalah pernyataan bahwa P = NP menyiratkan P = PH; itu sepele bahwa P = CC menyiratkan P = NP untuk setiap kelas CC yang mengandung NP. Immerman hanya berkomentar "jika P = NP lalu PH = NP" , mungkin karena P = NP dapat digunakan dengan definisi oracle dari PH untuk menunjukkan secara induktif bahwa seluruh hierarki runtuh.)

Pertanyaanku adalah:

Seberapa jauh P = NP dapat diamplifikasi dengan cara ini?

Secara khusus, apa kelas CC terbesar yang diketahui 'sehingga P = NP menyiratkan P = CC', dan kelas CC terkecil sehingga P = NP menyiratkan CC = NP? Ini akan memungkinkan P = NP digantikan oleh pertanyaan yang setara CC = CC '. P tampaknya kelas yang agak kuat, yang tampaknya memberikan sedikit "ruang gerak" untuk argumen yang mencoba memisahkannya dari NP: seberapa jauh ruang gerak dapat diperkuat?

Tentu saja saya juga akan tertarik pada argumen yang menunjukkan bahwa P = PH adalah batas dari pendekatan ini.

Sunting: perhatikan pertanyaan yang berkaitan erat. Mengapa P = NP tidak menyiratkan P = AP (yaitu P = PSPACE)? yang berfokus pada arah lain, mengapa kami tidak memiliki bukti bahwa P = PSPACE. Jawaban di sana oleh Kaveh dan Peter Shor berpendapat bahwa jumlah pergantian sedang diperbaiki adalah kuncinya. Pertanyaan terkait lainnya adalah masalah keputusan yang tidak diketahui berada di PH tetapi akan di P jika P = NP yang menanyakan masalah kandidat; jawaban di sana juga dapat digunakan untuk menyusun jawaban untuk pertanyaan ini, meskipun kelas-kelas ini agak artifisial (terima kasih kepada Tsuyoshi Ito karena telah menunjukkan ini). Dalam pengaturan yang lebih umum, Runtuh waktu kerja dan bergantian mesin turing terikat menanyakan apakah keruntuhan lokal di tingkat mana pun dalam hierarki bergantian menginduksi keruntuhan ke atas, seperti yang terjadi dengan hierarki waktu polinomial.

cc.complexity-theory reference-request complexity-classes conditional-results polynomial-hierarchy András Salamon
sumber

Terkait (promosi diri yang tidak tahu malu): Masalah keputusan yang tidak diketahui berada di PH tetapi akan berada di P jika P = NP .

Tsuyoshi Ito

Sebagai cara memformalkan bahasa apa yang ada dalam P jika P = NP, Regan memperkenalkan kelas kompleksitas H. Bahasa adalah dalam H jika dan hanya jika L berada di P relatif terhadap setiap oracle sehingga P = NP . Jadi, adalah dalam H jika pernyataan P = NP P relativizes. PH H Waktu-waktu alternatif . Dari teorema Toda, dan beberapa lemmas dalam teorema Toda, juga benar bahwa H P untuk setiap . (Pada dasarnya, setiap oracle memuaskan P

L

$L$

^{O}

$^O$

O

$O$

^{O}

$^O$

^{O}

$^O$

L

$L$

⟹ L \in

$\implies L \in$

\subseteq

$\subseteq$

\subseteq

$\subseteq$

(O (\log \log n), p o l y)

$(O(\log \log n), \rm{poly})$

\subseteq

$\subseteq$

^{{m o d}_{q} P}

$^{\rm{mod}_q \rm{P}}$

q

$q$

^{O}

$^O$ = NP memberikan batas atas baru pada H. Terbuka apakah H = PH.)

^{O}

$^O$

Russell Impagliazzo

@Russell: terima kasih! Komentar itu terdengar seperti jawaban.

András Salamon

Akhirnya menemukan referensi ke kelas Ken Regan : lihat definisi 6.3 dari "Kumpulan Indeks dan Presentasi Kelas Kompleksitas", tersedia di: citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.32.8927 . Versi resmi di: dx.doi.org/10.1016/0304-3975(95)00146-8

H

$H$

Joshua Grochow

Biarkan f (n) menjadi fungsi yang tidak terikat. H tidak terkandung dalam Alternatif-Waktu (f (n), poli) dan jika Anda dapat membuktikan P = NP menyiratkan P = Alternatif-Waktu (f (n), poli) maka NP berbeda dari L.

Lance Fortnow

Jawaban:

Dari komentar Russell Impagliazzo :

Sebagai cara memformalkan bahasa apa yang ada di jika , Regan memperkenalkan kelas kompleksitas . Sebuah bahasa adalah di jika dan hanya jika adalah di relatif terhadap setiap oracle sehingga . Dengan demikian, ada di jika pernyataan relativizes. $\mathsf{P}$ $\mathsf{P}=\mathsf{NP}$ $\mathsf{H}$ $L$ $\mathsf{H}$ $L$ $\mathsf{P}^O$ $O$ $\mathsf{P}^O=\mathsf{NP}^O$ $L$ $\mathsf{H}$ $\mathsf{P}=\mathsf{NP} \implies L\in\mathsf{P}$ $\mathsf{PH} \subseteq \mathsf{H} \subseteq \mathsf{AltTime}(O(\lg\lg n),\mathsf{poly})$ . Dari teorema Toda, dan beberapa lemmas dalam teorema Toda, benar juga bahwa untuk setiap . Pada dasarnya, setiap oracle yang memuaskan memberikan batas atas baru pada . Terbuka apakah . $\mathsf{H} \subseteq \mathsf{P}^{\mathsf{mod}_q \mathsf{P}}$ $q$ $\mathsf{P}^O=\mathsf{NP}^O$ $\mathsf{H}$ $\mathsf{H}=\mathsf{PH}$

Dan dari komentar Lance Fortnow :

Biarkan menjadi fungsi yang tidak terikat. tidak terkandung dalam dan jika Anda dapat membuktikan menyiratkan lalu berbeda dari . $f(n)$ $\mathsf{H}$ $\mathsf{AltTime}(f(n),\mathsf{poly})$ $\mathsf{P}=\mathsf{NP}$ $\mathsf{P}=\mathsf{AltTime}(f(n),\mathsf{poly})$ $\mathsf{NP}$ $\mathsf{L}$

Untuk definisi lihat definisi 6.3 di $\mathsf{H}$

Kenneth W. Regan, " Kumpulan indeks dan presentasi kelas kompleksitas ", 1999

Kaveh
sumber

@Josh, mengenai komentar Lance, saya merasa saya kehilangan sesuatu karena tidak terikat dan AltTime (f, poly) mengandung H menurut komentar Russel.

f (n) = \lg \lg n

$f(n) = \lg \lg n$

Kaveh

Saya bingung tentang sesuatu. Mengapa Josh Grochow tidak menjawab pertanyaan sebelumnya tentang topik ini ( cstheory.stackexchange.com/a/2039/1575 ) pada dasarnya menjawab pertanyaan Regan juga? Yaitu, mengapa itu tidak memberikan contoh bahasa L yang ada di P jika P = NP dengan argumen relativizing, tapi itu tidak di PH jika P! = NP? Dan mengapa tidak karena itu menunjukkan bahwa jika P! = NP, maka H benar-benar lebih besar dari PH?

Scott Aaronson

Sebenarnya, jawaban yang mungkin muncul pada saya. Apakah masalah yang, dalam konstruksi Grochow, definisi bahasa L akan sangat tergantung pada oracle O?

Scott Aaronson

@Scott: Memang, kemungkinan jawaban Anda benar, karena string mana yang digunakan untuk diagonalisasi (dan memang, apakah dimasukkan ke dalam atau keluar dari L) akan tergantung pada oracle. Secara lebih rinci, jika , bahasa adalah terbatas, sehingga berbeda untuk berbeda hanya berbeda. Tetapi jika kita menganggap semua sedemikian rupa sehingga , maka untuk berbeda ini bahkan tidak dapat menjadi p-ekuivalen, karena rangkaian orakel ini adalah subset padat dari .

P^{O} = N P^{O}

$P^O = NP^O$

L

$L$

L

$L$

O

$O$

O

$O$

P^{O} \neq N P^{O}

$P^O \neq NP^O$

L

$L$

O

$O$

2^{Σ^{*}}

$2^{\Sigma^*}$

Joshua Grochow

Seperti yang saya tulis dalam jawaban saya untuk pertanyaan lain, mari kita buat argumen yang konstruktif dan seragam dalam jumlah pergantian dengan memberikan algoritma yang memecahkan dengan asumsi bahwa kita memiliki algoritma waktu polinomial untuk SAT dan melihat apa yang akan kita dapatkan jika tidak konstan. $\Sigma^P_k$ $k$

Biarkan menjadi DTM dengan dua input dan . Anggap saja sebagai verifikasi untuk masalah . $M$ $x$ $y$ $\mathsf{NP}$

Biarkan menjadi algoritma yang mengubah TM ke sirkuit ukuran yang menghitung pada input ukuran untuk langkah. $Cook(M, \vec{n}, t)$ $M$ $s(\vec{n},t) \in \mathsf{poly}$ $M$ $\vec{n}$ $t$

Asumsikan bahwa dan ada algoritma deterministik yang memecahkan masalah ekstensi sertifikat Circuit-SAT dalam waktu . $\mathsf{P}=\mathsf{NP}$ $A$ $p\in\mathsf{poly}$

Dengan bahan-bahan ini kami mendefinisikan sebuah algoritma untuk TQBF yang memberikan formula Boolean yang dikuantifikasi, secara rekursif menghilangkan inner-quantifier yang paling dan menggantinya dengan yang gratis quantifier. Biarkan menjadi ukuran rumus pada langkah ke- , maka kita memiliki . Jika rumus memiliki quantifiers kita berakhir dengan mana adalah ukuran rumus TQBF yang diberikan sebagai input. $s_i$ $i$ $s_{i+1} = s\circ p(s_i)$ $k$ $q(n) = (s \circ p)^k(n)$ $n$

Jika konstan, maka . Karena nilai rangkaian dalam kami memiliki algoritme waktu polinomial. $k$ $q(n) \in \mathsf{poly}$ $\mathsf{P}$

Jika maka bukan waktu polinomial lagi, kita mendapatkan algoritma yang ada di . Misal jika kita mendapatkan algoritma kuasipolinomial-waktu. Untuk kita tidak mendapatkan apa-apa nontrivial. $k \in \omega(1)$ $q(n)$ $n^{2^{O(k)}}$ $k = \lg \lg n$ $k = \lg n$

Saya pikir apa yang kami benar-benar tertarik adalah kelas terbesar sehingga mana adalah teori yang cukup kuat untuk memformalkan semua arus kita. hasil (mis. Anda dapat mengambilnya ) karena poin utama dari hasil ini adalah untuk membuatnya lebih mudah untuk membuktikan . $C$

T ⊢ P = N P \to P = C

$T \vdash \mathsf{P} = \mathsf{NP} \to \mathsf{P}=C$

T

$T$

Z F C

$\mathsf{ZFC}$

P \neq N P

$\mathsf{P} \neq \mathsf{NP}$

Jika kita mengambil teori yang lebih lemah hasilnya mungkin masih menarik, namun itu bukan batas atas nilai . Ketika Regan menggunakan relativization untuk mendefinisikan ia pada dasarnya membatasi argumen kepada mereka yang merelatifikasi. Jika kita menggunakan hasil yang tidak relativize kita mungkin mendapatkan kelas yang lebih besar dari yang akan sama dengan jika . $C$ $\mathsf{H}$ $\mathsf{H}$ $\mathsf{P}$ $\mathsf{P}=\mathsf{NP}$

Sebagai catatan yang lebih filosofis, saya pribadi tidak menyukai gagasan berpikir tentang relativisasi sebagai realitas alternatif atau dunia. Pernyataan dalam "dunia yang direlatifikasi" sendiri tidak memberi kami informasi apa pun tentang pernyataan tersebut dalam pengaturan yang tidak terkait. Sebagai contoh dari ini ambil yang sebagian besar dari kita tidak percaya benar tetapi versi relativized benar wrt oracle acak dengan probabilitas 1. Sebagai contoh lain mengambil yang benar tetapi menjadi false wrt oracle acak dengan probabilitas 1. $\mathsf{BPP} = \mathsf{PP}$ $\mathsf{IP} = \mathsf{PSpace}$

Saya juga menemukan ide bahwa hanya ada satu cara yang benar untuk merelatifkan kelas kompleksitas yang bermasalah yang menyebabkan banyak kesalahpahaman (seperti berpikir relativization sebagai operasi fungsional pada kelas kompleksitas dalam arti ekstensional mereka, relativiasi merupakan modifikasi dari model perhitungan , bukan kelas fungsi atau bahasa). Saya pikir melihat relativizations sebagai kerangka kerja komputasi (interaktif) yang dimodifikasi lebih berguna. Dengan cara ini ada banyak cara yang berguna untuk merelatifkan kelas kompleksitas (dalam arti yang disengaja). Untuk mendapatkan informasi tentang pengaturan yang tidak terkait dengan kerangka kerja yang direlatifikasi, kita memerlukan semacam prinsip transfer yang serupa dengan prinsip transfer dalam analisis non-standar. Perhatikan bahwa memilih beberapa metode relativisasi khusus untuk kelas yang mempertahankan hubungan yang diketahui antar kelas tidak memberi kita prinsip transfer (ini adalah kriteria utama yang biasanya digunakan dalam literatur untuk memutuskan apa yang merupakan "relativiasi yang tepat dari suatu kelas).

Kaveh
sumber

Saya setuju dengan "melihat relativizations sebagai kerangka perhitungan interaktif lebih berguna menurut pendapat saya" dengan cara tertentu. Yaitu presentasi relativizations dapat dibuat lebih intuitif untuk memahami dengan memulai dengan situasi di mana mesin (dengan akses oracle interaktif) diberikan pertama, dan lawan diizinkan untuk memilih bahasa untuk oracle. Kemudian seseorang beralih ke situasi di mana bahasa oracle (kompleks) diberikan pertama kali, dan mesin sekarang dapat disesuaikan dengan dunia yang diberikan oleh oracle tertentu.

Thomas Klimpel