Dalam pertanyaan ini, rumus 3CNF berarti rumus CNF di mana setiap klausa persis melibatkan tiga variabel yang berbeda . Untuk konstanta 0 < s <1, Gap-3SAT s adalah masalah janji berikut:
Gap-3SAT s
Instance : Sebuah 3CNF rumus φ.
Ya-janji : φ memuaskan.
No-janji : tidak ada tugas kebenaran memuaskan lebih dari s sebagian kecil dari klausul φ.
Salah satu cara yang setara untuk menyatakan teorema PCP terkenal [AS98, ALMSS98] adalah bahwa terdapat konstanta 0 < s <1 sehingga Gap-3SAT s adalah NP-complete.
Kami mengatakan bahwa rumus 3CNF berpasangan B-berpasangan jika setiap pasangan variabel berbeda muncul di paling banyak klausa B. Misalnya, rumus 3CNF ( x 1 ∨ x 2 ∨ x 4 ) ∧ (¬x 1 ∨¬x 3 ∨ x 4 ) ∧ ( x 1 ∨ x 3 ∨¬x 5 ) berpasangan 2-terikat tetapi tidak berpasangan 1 -batas karena mis. pasangan ( x 1 , x 4 ) muncul di lebih dari satu klausa.
Pertanyaan . Apakah terdapat konstanta B ∈ℕ, sebuah > 0, dan 0 < s <1 sehingga Gap-3SAT s adalah NP-lengkap bahkan untuk formula 3CNF yang berpasangan B -bounded dan terdiri dari setidaknya sebuah 2 klausa, di mana n Apakah jumlah variabel?
Keterbatasan berpasangan jelas menyiratkan bahwa hanya ada klausa O ( n 2 ). Bersama dengan batas bawah kuadratik pada jumlah klausa, secara kasar dikatakan bahwa tidak ada pasangan variabel yang berbeda muncul dalam klausa yang jauh lebih banyak daripada rata-rata.
Untuk Gap-3SAT, diketahui bahwa kasus jarang sulit : terdapat 0 konstan < s <1 sehingga Gap-3SAT s adalah NP-lengkap bahkan untuk rumus 3CNF di mana setiap variabel terjadi tepat lima kali [Fei98]. Di sisi lain, kasus padat mudah : Max-3SAT mengakui sebuah POMG untuk formula 3CNF dengan Ω ( n 3 ) klausa yang berbeda [AKK99], dan karena itu Gap-3SAT s dalam hal ini adalah dalam P untuk setiap konstan 0 < s <1. Pertanyaannya adalah tentang pertengahan dari dua kasus ini.
Pertanyaan di atas muncul awalnya dalam studi kompleksitas komputasi kuantum, lebih khusus dua-membuktikan sistem bukti interaktif satu putaran dengan sistem provers terjerat ( MIP * (2,1) ). Tapi saya pikir pertanyaannya mungkin menarik dengan sendirinya.
Referensi
[AKK99] Sanjeev Arora, David Karger, dan Marek Karpinski. Skema perkiraan waktu polinomial untuk contoh padat masalah NP-keras. Jurnal Ilmu Komputer dan Sistem , 58 (1): 193–210, Februari 1999. http://dx.doi.org/10.1006/jcss.1998.1605
[ALMSS98] Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, dan Mario Szegedy. Verifikasi bukti dan kekerasan masalah perkiraan. Jurnal ACM , 45 (3): 501–555, Mei 1998. http://doi.acm.org/10.1145/278298.278306
[AS98] Sanjeev Arora dan Shmuel Safra. Pemeriksaan probabilistik bukti: Karakterisasi baru NP. Jurnal ACM , 45 (1): 70-122, Januari 1998. http://doi.acm.org/10.1145/273865.273901
[Fei98] Uriel Feige. Ambang batas ln n untuk perkiraan penutup yang ditetapkan. Jurnal ACM , 45 (4): 634-652, Juli 1998. http://doi.acm.org/10.1145/285055.285059
sumber
Jawaban:
Bukan jawaban lengkap, tapi mudah-mudahan tutup. Ini sangat dekat dengan komentar Luca di atas. Saya percaya jawabannya adalah bahwa setidaknya ada konstanta B ∈ℕ, a > 0, dan 0 < s <1 sehingga Gap-3SAT s adalah NP-lengkap bahkan untuk formula 3CNF yang berpasangan B- terikat dan terdiri dari setidaknya klausa, untuk konstanta ϵ .an2−ϵ ϵ
Buktinya adalah sebagai berikut. Pertimbangkan GAP-3SAT s misalnya φ pada N variabel di mana setiap variabel muncul paling 5 kali. Ini NP-lengkap, seperti yang Anda katakan dalam pertanyaan.s ϕ N
Sekarang kita membuat instance baru sebagai berikut:Φ
Jumlah total variabel kemudian . Catatan Φ memiliki 2 N n 2 klausa perbandingan dan 5m=nN Φ 2Nn2 klausa yang diwarisi, dengan total1153Nn2 klausa. Mengambiln=113Nn2 kita memiliki m = N k + 1 dan jumlah total klausul C = 11n=Nk m=Nk+1 . Kami mengambilk=ϵ-1-1, jadiC∝m2-ϵ.C=113N2k+1=113m2−1k+1 k=ϵ−1−1 C∝m2−ϵ
Selanjutnya, berpasangan 8 (maks. 2 dari klausa perbandingan dan 6 dari klausa yang diwarisi).Φ
Akhirnya, jika tidak memuaskan, maka setidaknya ( 1 - s ) N klausa tidak puas. Sekarang, jika y i a ≠ y i b untuk a , b maka setidaknya n - 1 klausa tidak puas. Perhatikan bahwa untuk memenuhi ( 1 - sϕ (1−s)N yia≠yib a,b n−1 klausa yang tidak terpenuhi dalam satu set klausa yang diwarisi untuk memperbaiki a , b maka penugasan variabel y : a , y :(1−s)N a,b y:a dan y : ( a + b ) harus berbeda setidaknya 1 - dtky:b y:(a+b) posisi, meninggalkan setidaknya1-dtk1−s5N perbandingan klausa yang tidak memuaskan. Ini harus berlaku untuk setiap pilihanadanb, jadi setidaknya≈1-dtk1−s5N(n−1) a b Klausa perbandinganCharus tetap tidak puas secara total agar klausa yang diwarisi cukup untuk dipenuhi. Namun jika Anda melihat ekstrim lain di mana semua klausa perbandingan terpenuhi, maka(1-s)Nn≈1−s5Nn2=3(1−s)11C Klausa C tidak memuaskan. Oleh karena itu kesenjangan tetap (meskipun dikurangi) dengan s ′ = 4 + s(1−s)Nn2=(1−s)m2k+1k+1=(1−s)C .s′=4+s5
Konstanta mungkin perlu diperiksa ulang.
sumber