Kondisi untuk keterlacakan 3SAT-Kepuasan

Yang ingin saya tanyakan secara khusus adalah apakah ada kondisi yang menarik pada persentase penugasan yang memenuhi formula 3SAT untuk menjamin bahwa masalah tersebut dapat diselesaikan.

Misalkan misalnya kelas masalah 3SAT yang dari kemungkinan penugasan memenuhi rumus boolean; dapatkah kita menemukan tugas yang memuaskan secara efisien? Untuk apa masalah yang dihasilkan dalam P? $\epsilon(n) 2^n$ $2^n$ $\epsilon$

Edit catatan: Diganti dengan untuk menghapus kebingungan. $\epsilon$ $\epsilon(n)$

cc.complexity-theory ds.algorithms sat np Rafi Witten
sumber

Pengamatan sederhana: Jika

paling banyak kebalikannya dari kecil secara polin, maka pengambilan sampel yang seragam

kali akan menghasilkan solusi dalam waktu polinomial yang diharapkan. Jadi jika

adalah antara 1 dan 1 / poli (n), masalah ini mudah (ada di ZPP).

ϵ

$\epsilon$

1 / ϵ

$1/\epsilon$

ϵ

$\epsilon$

Robin Kothari

sama halnya, jika 1 / eps adalah quasipolynomial, maka Anda memiliki algoritma waktu quasipoly acak, yang dengan sendirinya akan mengejutkan

Suresh Venkat

Jawaban:

Iya. Jika adalah konstanta (atau ), dan Anda berjanji bahwa setidaknya dari semua kemungkinan penugasan memenuhi input 3CNF, maka Anda dapat menemukan penugasan tersebut dalam polinomial deterministik- waktu. $0< \epsilon <1$ $1/\textit{polylog}(n)$ $\epsilon 2^n$

Algoritma tidak sulit:

Klaim: Di bawah janji menyatakan, harus ada ukuran yang konstan set variabel yang menyentuh semua klausul dalam 3CNF, dalam arti bahwa setiap 3-klausul harus berisi variabel dari . $S$ $S$

Bukti klaim (sketsa): Jika tidak, harus ada keluarga yang cukup besar dengan 3 klausa dari 3CNF, di mana setiap variabel hanya muncul satu kali. Tetapi keluarga ini, ketika cukup besar, sudah kurang dari bagian dari tugas yang memuaskan. QED $\epsilon$

Dengan demikian, Anda dapat menjalankan lebih dari semua kemungkinan (jumlah konstan) dari tugas ke . Di bawah setiap penetapan tetap untuk , 3CNF menjadi 2CNF, dengan asumsi bahwa mencapai 3CNF asli. Sekarang, Anda dapat menggunakan algoritma deterministik polytime yang dikenal untuk menemukan tugas yang memuaskan untuk rumus 2CNF. Secara keseluruhan, Anda mendapatkan batas waktu polinomial atas. $S$ $S$ $S$

Algoritma untuk 2SAT adalah saya pikir sudah di kertas 1971 S. Cook yang terkenal.

Algoritma untuk 3CNF adalah dari: L. Trevisan Catatan tentang Penghitungan Perkiraan Deterministik untuk k-DNF Di Proc. dari APPROX-RANDOM, Springer-Verlag, halaman 417-426, 2004

Makalah asli menunjukkan hasil untuk 3CNF adalah: E. Hirsch, Algoritma deterministik cepat untuk formula yang memiliki banyak tugas yang memuaskan , Jurnal IGPL, 6 (1): 59-71, 1998

Iddo Tzameret
sumber

ϵ

$\epsilon$

ϵ = 1 / p o l y l o g (n)

$\epsilon = 1/polylog(n)$

Bagaimana Anda membangun S?

Radu GRIGore

C_{1}

$C_1$

C_{2}

$C_2$

C_{1}

$C_1$