Apakah NP Hampir-2-SAT-keras?

10

Apakah masalah CNF SAT NP sulit ketika jumlah total (tetapi bukan lebar) dari klausa 3-atau-lebih istilah dibatasi di atas oleh konstanta? Bagaimana dengan spesifik ketika hanya ada satu klausa seperti itu?

np-hardness sat upper-bounds dspyz
sumber

8

Jika hanya ada satu seperti klausul dengan lebih dari 2 hal, memecahkan rumus tersebut sepele di . Jika memiliki syarat, coba masing-masing penugasan parsial yang memenuhi , kemudian selesaikan rumus 2-SAT yang tersisa menggunakan metode linear-time yang diketahui. Akhirnya Anda akan menemukan solusi untuk seluruh rumus atau membuktikan bahwa itu tidak memuaskan dalam waktu , di mana tidak dapat melebihi jumlah variabel dalam seluruh rumus.

c

$c$

P

$P$

c

$c$

n

$n$

n

$n$

c

$c$

O (n^{2})

$O(n^2)$

n

$n$

Kyle Jones

@KyleJones Tapi satu klausa dengan literal memiliki tugas yang memuaskan, bukan hanya . Karena tidak dibatasi dalam pertanyaan, pendekatan ini memberikan algoritma waktu eksponensial.

k

$k$

2^{k} - 1

$2^k-1$

k

$k$

k

$k$

David Richerby

2

@ DavidRicherby Untuk memenuhi klausa Anda hanya perlu membuat salah satu dari literal mengevaluasi benar. Setelah itu klausa dapat diabaikan dan Anda hanya memiliki rumus 2-SAT yang tersisa. literal berarti Anda hanya perlu mencoba tugas .

k

$k$

k

$k$

Kyle Jones

14

Perlu dicatat bahwa masalahnya menjadi NP-keras ketika pembatasan sedikit santai.

Dengan jumlah klausa tetap yang juga memiliki ukuran terikat, jumlah rata-rata literal dalam klausa mendekati 2 seperti yang diinginkan, dengan mempertimbangkan sebuah instance dengan variabel yang cukup. Seperti yang Anda tunjukkan, maka ada batas atas sederhana yang jumlahnya banyak jika ukuran klausa dibatasi.

Sebaliknya, jika jumlah rata-rata literal per klausa adalah paling sedikit untuk beberapa fix (tapi kecil sekali pun) , maka masalahnya adalah NP-hard. $2 + \epsilon$ $\epsilon > 0$

Ini dapat ditunjukkan dengan mengurangi 3SAT untuk masalah ini, dengan memperkenalkan klausa baru dengan 2 literal yang sepele memuaskan. Misalkan ada klausa dalam contoh 3SAT; untuk mengurangi ukuran klausa rata-rata menjadi , cukup menambahkan klausa baru dengan dua literal. Karena adalah tetap dan positif, turunan baru berukuran polinomial. $m$ $(2+\epsilon)$ $m(1 - \epsilon)/\epsilon$ $\epsilon$

Pengurangan ini juga menunjukkan bahwa bahkan versi di mana klausa "besar" dibatasi hingga 3 liter adalah NP-hard.

Kasus yang tersisa adalah ketika beberapa klausa besar tidak memiliki ukuran yang dibatasi; setiap klausa besar tampaknya membuat masalah semakin sulit. Lihat makalah SODA 2010 oleh Pǎtraşcu dan Williams untuk kasus dua klausa: mereka berpendapat bahwa jika ini dapat dilakukan dalam waktu sub-kuadrat maka kita akan memiliki algoritma yang lebih baik untuk SAT. Mungkin ada perluasan argumen mereka ke lebih banyak klausa, yang akan memberikan bukti bahwa batas atas Anda tidak dapat ditingkatkan (modulo beberapa bentuk hipotesis waktu eksponensial).

András Salamon
sumber

hanya terkait secara tangensial, tetapi ada makalah ECCC baru-baru ini yang merumuskan "hampir 2-SAT" dengan cara yang berbeda dan membuktikan kekerasan yang kuat: eccc.hpi-web.de/report/2013/159

Sasho Nikolov

8

OK aku mengerti. Jawabannya adalah tidak. Ini dapat diselesaikan dalam waktu-poli. Untuk setiap klausa 3 atau lebih istilah, pilih satu literal dan setel menjadi true. Kemudian selesaikan masalah 2-sat yang tersisa. Jika ada yang memberikan solusi, maka itu adalah solusi untuk masalah keseluruhan. Karena jumlah klausa 3-atau-lebih-tetap adalah (katakanlah c), maka jika semua klausa tersebut memiliki ukuran <= m, maka ini berjalan dalam O (m ^ (c) * n). O (m ^ c) untuk melalui setiap pilihan yang mungkin, kali O (n) untuk menyelesaikan masalah 2-sat yang tersisa.

dspyz
sumber

Tetapi pertanyaannya secara eksplisit mengatakan bahwa tidak terikat, jadi ini bukan algoritma waktu polinomial.

m

$m$

David Richerby

Yaitu, karena m secara implisit dibatasi oleh jumlah atom. Jelas, klausa tidak dapat memiliki lebih banyak literal daripada ada atom dalam masalah. Mungkin saya harus mengklarifikasi m <= n

dspyz

Apakah NP Hampir-2-SAT-keras?

Jawaban: