Menghitung informasi apa pun tentang Max-3SAT

Untuk formula 3CNF $C$ biarkan $M(C)$ menjadi jumlah maksimal klausul puas dalam setiap penugasan ke $C$ . Diketahui bahwa Max-3SAT sulit diperkirakan (tunduk pada P ≠ NP), yaitu tidak ada algoritma polytime yang inputnya adalah rumus 3CNF , dan yang outputnya adalah angka sehingga berada dalam faktor multiplikasi$C$$M'$$M(C)$$1+c$ dari $M'$ , di mana $c>0$ adalah konstanta positif absolut.

$M(C) \bmod p$$p$$C$$N$$\log_2 N-B$$M(C)$$B$$B$$M(C)$

Saya minta maaf jika pertanyaannya memiliki jawaban yang terkenal, karena saya bukan ahli teori kompleksitas dengan latar belakang.

Berikut adalah argumen bahwa jika Anda bisa menyelesaikan Max 3SAT pada contoh m-klausa yang diberikan sejumlah bit nasihat, maka hierarki polinomial akan runtuh.

Perbaiki masalah NP-selesai L. Dari teorema Cook, kita tahu transformasi f () dari input x untuk L menjadi rumus 3SAT f (x), sehingga

1) jika x ∈ L maka M ( f ( x ) ) = $x\in L$$M(f(x)) = m$

2) jika x ∈ L maka M ( f ( x ) ) = m - $x\in L$$M(f(x)) = m-1$

di mana m adalah jumlah klausa dalam f ( $m$ ) .$f(x)$

Kami juga memiliki teorema Kadin, yang mengatakan bahwa, jika diberikan k input x 1 , ... , x k dari masalah NP-complete, Anda memiliki algoritma waktu polinomial yang membuat ≤ k - 1 kueri ke oracle NP dan menentukan jawaban yang benar untuk k NP masalah x i ∈ ? L , maka hirarki polinomial runtuh.$k$$x_1,\ldots,x_k$$\leq k-1$$k$$x_i \in ? L$

Misalkan kita memiliki algoritma yang memecahkan Max SAT pada input m-klausa yang diberikan k bit saran. Kami akan menggunakan hasil Hastad untuk membangun sebuah algoritma seperti pada premis teorema Kadin.

Mulai dari K = 2 k + 1 input x 1 , ... , x K masalah L . Terapkan teorema Cook ke masing-masing. Setelah beberapa normalisasi (yang dapat dilakukan dengan menetapkan bobot pada klausa, atau menduplikasinya jika kita tidak ingin menggunakan bobot), kita membuat rumus K F 1 , … , F K di mana, untuk m tertentu$K=2^k+1$$x_1,\ldots,x_K$$L$$K$$F_1,\ldots,F_K$$m$ :

1) M ( F 1 ) = m - 1 jika x 1 ∈ L dan M ( F 1 ) = m - 2 sebaliknya$M(F_1)= m-1$$x_1 \in L$$M(F_1) = m-2$

2) M ( F 2 ) = m ⋅ ( m - 1 ) jika x 2 ∈ L dan M ( F 2 ) = m ⋅ ( m - 2 ) jika tidak$M(F_2) = m\cdot (m-1)$$x_2 \in L$$M(F_2) = m\cdot (m-2)$

...

k) M ( F K ) = m K - 1 ⋅ ( m - 1 ) jika x K ∈ L dan M ( F K ) = m K - 1 ⋅ ( m - 2 $M(F_K) = m^{K-1} \cdot (m-1)$$x_K\in L$$M(F_K) = m^{K-1} \cdot (m-2)$ jika tidak

Sekarang ambil persatuan rumus, yang dibangun di atas variabel menguraikan set, dan menyebutnya F . Jadi kita memiliki M ( F ) = M ( F 1 ) + ⋯ + M ( F k ) , dan kita dapat "membaca off" jawaban terhadap K masalah x i ∈ ? L dengan melihat dasar- m representasi M ( F ) . Jika kita dapat menghitung M ( F ) yang diberikan$F$$M(F) = M(F_1) + \cdots + M(F_k)$$K$$x_i \in? L$$m$$M(F)$$M(F)$$k$bit of advice, artinya kita dapat menemukan nilai 2 k sedemikian rupa sehingga salah satunya adalah M ( F ) . Kita kemudian dapat bertanya non-adaptif NP oracle apakah M ( F ) ≥ n i untuk masing-masing nilai kandidat n 1 , … , n 2 k yang kita hasilkan. Jadi kita telah dapat menyelesaikan 2 k + 1 instance dari masalah NP-complete dengan membuat 2 $2^k$$M(F)$$M(F) \geq n_i$$n_1,\ldots,n_{2^k}$$2^k+1$$2^k$ pertanyaan non-adaptif ke oracle NP, yang menyiratkan bahwa hierarki polinomial runtuh.

Menggunakan teorema Hastad bukan teorema Cook, dimungkinkan untuk mendorong ukuran F ke O ( 1 ) k ⋅ m, bukan m k , sehingga dimungkinkan untuk mendorong k untuk mencatat m , dan jumlah bit saran untuk mencatat log m . Memahami apa yang terjadi ketika Anda diberi log m - O ( 1 ) bit saran tampaknya sangat sulit.$F$$O(1)^k \cdot m$$m^k$$k$$\log m$$\log\log m$$\log m - O(1)$

Diedit untuk menambahkan: Krentel ( Kompleksitas Masalah Optimasi . J. Comput. Syst. Sci. 36 (3): 490-509 (1988) ) membuktikan bahwa menghitung nilai optimum dari masalah klik maksimum adalah lengkap untuk F P n P [ O ( l o g n ) ] , kelas fungsi dihitung dalam waktu polinomial dengan O ( l o g n ) query ke oracle NP. Kelengkapannya berada di bawah "satu pengurangan kueri," di mana fungsi f dapat direduksi menjadi fungsi g jika seseorang dapat menulis f ( x ) = $FP^{NP[O(log n)]}$$O(log n)$ 1 (g ( r 2 ( x ) ) untuk waktu polinom yang dapat dihitung r 1 dan r 2 . Agaknya hal yang sama berlaku untuk Max Clique. Sekarang, jika Max Clique memiliki algoritma waktu polinomial yang menghasilkan daftar nilai m o ( 1 ) yang mungkin, itu akan berada dalam F P N P [ o ( l o g n ) $f(x) = r_1(g(r_2(x))$$r_1$$r_2$$m^{o(1)}$$FP^{NP[o(logn)]}$ , karena Anda bisa menggunakan pencarian biner untuk menemukan yang optimal dengan sejumlah kueri yang merupakan log dari ukuran daftar.

Sekarang, jika kita memiliki F P N P [ O ( l o g n ) ] = F P N P [ o ( l o g n ) ] kita pasti akan memiliki P N P [ O ( l o g n ) ] = P n P [ o ( l o g n ) $FP^{NP[O(log n)]} = FP^{NP[o(log n)]}$$P^{NP[O(log n)]} = P^{NP[o(log n)]}$, yang merupakan kasus khusus untuk masalah keputusan, dan yang diketahui, oleh hasil Wagner (meningkatkan hasil Kadin yang berlaku untuk jumlah kueri yang konstan), untuk memecah hierarki polinomial. Tapi saya berpikir bahwa itu mungkin diketahui bahwa $FP^{NP[O(log n)]} = FP^{NP[o(log n)]}$ akan benar-benar menyiratkan P = NP. Tetapi bagaimanapun, hasil Krentel dan Kadin-Wagner harus cukup untuk memberikan bukti lain dari hasil Andy Drucker. Sekarang saya bertanya-tanya apakah itu sebenarnya bukti yang sama, yaitu, jika hasil Fortnow-Van Melkebeek bekerja, secara eksplisit atau implisit, melalui argumen "mensimulasikan permintaan NP dengan lebih sedikit pertanyaan NP".

Makalah survei yang bagus yang menjelaskan apa yang terjadi dengan masalah optimisasi dan kelas kueri terbatas:

http://www.csee.umbc.edu/~chang/papers/bqabh/npfsat.pdf

Saya ingin menyatakan satu alasan mengapa membuktikan NP-hardness dari masalah ini sulit.

Dalam komentar pada pertanyaan, Luca Trevisan memberikan cara yang bagus untuk menyatakan kembali masalah: Apakah masalah berikut ini terpecahkan dalam waktu polinomial untuk setiap k konstan ? Diberikan rumus CNF C dengan klausa m , menghasilkan paling banyak bilangan bulat m / k sehingga salah satunya sama dengan M ( C ). Di sini k terkait dengan B dengan k = 2 ^B .

Namun, mari kita menuntut lebih banyak. Yaitu, kami mempertimbangkan masalah berikut: diberi rumus CNF C , menghasilkan dua bilangan bulat sehingga salah satunya sama dengan M ( C ). Kami menyatakan masalah ini oleh Π. Masalahnya Π setidaknya sesulit masalah aslinya, jadi jika masalah aslinya NP-hard,, juga harus NP-hard.

Perhatikan bahwa Π adalah masalah hubungan. Salah satu jenis reduksi paling sederhana yang dapat digunakan untuk mengurangi beberapa masalah L ke masalah relasi Π adalah pengurangan Levin polinomial-waktu, yang merupakan kasus khusus dari pengurangan Turing polinomial-waktu di mana reduksi memanggil oracle hanya untuk Π sekali.

Kami mengklaim bahwa P ^{Π [1]} = P. Ini jelas menyiratkan bahwa NP⊈P ^{Π [1]} kecuali P = NP, yaitu, Π tidak NP-keras di bawah waktu polinomial Levin reducibilitas kecuali P = NP.

Bukti . Misalkan L ∈P ^{Π [1]} , atau dengan kata lain, ada pengurangan Levin dari L ke Π. Ini berarti bahwa ada pasangan ( f , g ) dari fungsi yang dihitung waktu polinomial f : {0,1} ^* → {0,1} ^* yang memetakan setiap instance x dari masalah L ke beberapa rumus CNF f ( x ) dan predikat komputasi polinomial-waktu g : {0,1} ^* × ℕ × ℕ → {0,1} sehingga g ( x , i , j ) = L(x ) jika i atau j sama dengan M ( f ( x )). (Di sini L ( x ) = 1 jika x adalah instance-ya dari L dan L ( x ) = 0 jika x adalah instance-bukan.)

Kami membuat algoritma waktu polinomial untuk L dari ini sebagai berikut. Biarkan x menjadi input.

1. Biarkan C = f ( x ), dan biarkan m menjadi jumlah pasal dalam C .
2. Temukan satu i ∈ {0, ..., m } sedemikian sehingga nilai g ( x , i , j ) adalah konstan independen dari j ∈ {0, ..., m }.
3. Keluarkan konstanta g ini ( x , i , 0).

Pada langkah 2, saya selalu ada karena i = M ( f ( x )) memenuhi syarat. Selain itu, algoritma ini tidak dapat menghasilkan jawaban yang salah karena g ( x , i , M ( f ( x ))) harus jawaban yang benar. Oleh karena itu, algoritma ini memecahkan L dengan benar. QED .

Jika saya tidak salah, ide yang sama dapat digunakan untuk membuktikan bahwa P ^{Π [ k ( n )]} ⊆DTIME [ n ^{O ( k ( n ))} ]]. Ini berarti bahwa NP⊈P ^{Π [ k ]} untuk setiap konstan k kecuali P = NP dan bahwa NP⊈P ^{Π [polylog]} kecuali NP⊆DTIME [2 ^polylog ]. Namun, gagasan ini saja tampaknya tidak mengesampingkan kemungkinan bahwa Π NP-hard di bawah reduksibilitas Turing polinomial-waktu.

Saya percaya bahwa kami dapat menunjukkan:

Klaim. Ada nilai 0 < c < 1 sehingga yang berikut ini benar. Misalkan ada algoritma poli-waktu deterministik itu, diberi m -clause 3-SAT misalnya φ , output daftar S paling banyak m c nilai-nilai, sehingga M ( φ ) ∈ S ; maka hierarki polinomial runtuh.$0 < c < 1$$m$$\phi$$S$$m^c$$M(\phi) \in S$

Buktinya menggunakan hasil Fortnow dan Santhanam pada ketidaklayakan kompresi contoh dari makalah mereka http://www.cs.uchicago.edu/~fortnow/papers/compress.pdf

Secara khusus, dengan melihat bukti Thm 3.1, saya percaya seseorang dapat mengekstrak yang berikut ini (saya akan memeriksa kembali ini segera):

"Teorema" [FS]. Ada bilangan bulat 0 < d ′ < d sehingga yang berikut ini benar. Misalkan di deterministik poli-waktu, seseorang dapat mengubah suatu OR dari n d Boolean formula (masing-masing dengan panjang ≤ n , dan menguraikan variabel-set) menjadi OR dari n d ' formula (lagi variabel-menguraikan dan panjang ≤ n ) , menjaga kepuasan / ketidakpuasan OR. Kemudian N P ⊆ c o N P / p o l y dan hierarki polinomial runtuh.$0 < d' < d$$n^d$$\leq n$$n^{d'}$$\leq n$$\mathsf{NP} \subseteq \mathsf{coNP/poly}$

Bukti klaim kami adalah pengurangan dari tugas kompresi-AT yang disebutkan dalam teorema [FS] di atas, ke masalah komputasi daftar- M ( ϕ ) . Misalkan ψ 1 , … , ψ n d adalah daftar rumus yang ATAU ingin kita kompres.$M(\phi)$$\psi_1, \ldots, \psi_{n^d}$

Langkah pertama: tentukan sirkuit ukuran polinomial Γ pada string input ( v , y 1 , … , y n d ) . Di sini string y i mengkodekan penugasan ke ψ i , dan v ∈ { 0 , 1 } d log n + 1 mengkodekan angka antara 0 dan n d .$\Gamma$$(v, y_1, \ldots, y_{n^d})$$y_i$$\psi_i$$v \in \{0, 1\}^{d \log n + 1}$$0$$n^d$

Kami telah Γ menerima iff baik v = 0 , atau ψ v ( y v ) = 1 .$\Gamma$$v = 0$$\psi_v(y_v) = 1$

Sekarang misalkan M ∗ ( Γ ) menyatakan nilai maksimum v , sehingga sirkuit terbatas Γ ( v , ⋅ , ... , ⋅ ) memuaskan. (Kuantitas ini selalu paling tidak 0).$M^*(\Gamma)$$v$$\Gamma(v, \cdot, \ldots, \cdot)$

Misalkan kita dapat secara efisien menghasilkan daftar S dari nilai yang mungkin untuk M ∗ ( Γ ) . Maka klaimnya adalah bahwa dalam daftar kami ψ 1 , ... , ψ n d , kita dapat membuang semua ψ i yang i ∉ S ; daftar yang dihasilkan berisi formula yang memuaskan jika yang asli lakukan. Saya harap ini jelas dengan inspeksi.$S$$M^*(\Gamma)$$\psi_1, \ldots, \psi_{n^d}$$\psi_i$$i \notin S$

Kesimpulan: kita tidak dapat secara andal menghasilkan daftar S dari ≤ n d ′ nilai yang mungkin untuk M ∗ ( Γ ) , kecuali hierarki poli runtuh.$S$$\leq n^{d'}$$M^*(\Gamma)$

Langkah Kedua: Kami mengurangi dari masalah komputasi daftar M ∗ ( Γ ) ke masalah komputasi daftar M ( ϕ ) untuk instance 3-SAT ϕ .$M^*(\Gamma)$$M(\phi)$$\phi$

Untuk melakukan ini, pertama-tama kita jalankan pengurangan Cook pada Γ untuk mendapatkan instance 3-SAT ϕ 1 dengan ukuran m = p o l y ( n d ) . ϕ 1 memiliki variabel-set yang sama dengan Γ , bersama dengan beberapa variabel tambahan. Paling penting untuk tujuan kita, ϕ 1 ( v , ⋅ ) memuaskan jika Γ ( v , ⋅ ) memuaskan.$\Gamma$$\phi_1$$m = poly(n^d)$$\phi_1$$\Gamma$$\phi_1(v, \cdot)$$\Gamma(v, \cdot)$

Kami menyebut ϕ 1 `kendala kuat '. Kami memberikan masing-masing kendala ini bobot 2 m (dengan menambahkan kendala duplikat).$\phi_1$$2m$

Kemudian kita tambahkan satu set `kendala lemah ' ϕ 2 yang menambahkan preferensi untuk indeks v (didefinisikan pada langkah 1) setinggi mungkin. Ada satu kendala untuk setiap bit v t dari v , yaitu [ v t = 1 ] . Kami membiarkan t -th bit paling signifikan dari v memiliki kendala berat m / 2 t - 1 . Karena v memiliki panjang d log n + 1 , bobot ini dapat dibuat integral (kita hanya perlu pad untuk membiarkan $\phi_2$$v$$v_t$$v$$[v_t = 1]$$t$$v$$m/2^{t-1}$$v$$d \log n + 1$$m$ menjadi kekuatan 2).

Akhirnya, mari ϕ = ϕ 1 ∧ ϕ 2 menjadi output dari pengurangan kami.$\phi = \phi_1 \wedge \phi_2$

Untuk menganalisis ϕ , misalkan ( v , z ) menjadi variabel-set ϕ , dengan v seperti sebelumnya. Catatan pertama yang diberikan setiap penugasan ke ( v , z ) , seseorang dapat menyimpulkan nilai v dari kuantitas N ( v , z ) = (berat total ϕ - kendala dipenuhi oleh v , z ). Ini mengikuti dari desain hirarki bobot-kendala (mirip dengan teknik dari jawaban Luca). Demikian pula, nilai maksimum yang dapat dicapai $\phi$$(v,z)$$\phi$$v$$(v, z)$$v$$N(v, z) =$$\phi$$v, z$
$M(\phi)$ is achieved by a setting $(v, z)$ that satisfies all strong constraints, and where (subject to this) $v$ is as large as possible. This $v$ is the largest index for which $\Gamma(v, \cdot)$ is satisfiable, namely $M^*(\Gamma)$. (Note, it is always possible, by setting $v =$ all-0, to satisfy all strong constraints, since in that case $\Gamma(v, \cdot)$ is satisfiable.)

Oleh karena itu, jika kita diberi daftar S dari nilai yang mungkin dari M ( ϕ ) , kita dapat memperoleh daftar | S | nilai yang mungkin dari M * ( Γ ) . Dengan demikian kita tidak dapat memiliki | S | ≤ n d ′ kecuali hierarki poli runtuh. Ini memberikan Klaim, karena n d ′ = m Ω ( 1 ) .$S$$M(\phi)$$|S|$$M^*(\Gamma)$$|S| \leq n^{d'}$$n^{d'} = m^{\Omega(1)}$