Memverifikasi seluk-beluk bukti asli Karp bahwa SAT memiliki pengurangan waktu polinomial menjadi 3SAT

Singkatnya, pertanyaan saya adalah: apakah bukti asli Karp yang mengurangi SAT menjadi 3SAT tidak perlu diuraikan? Dengan rincian sebagai berikut.

Dalam makalahnya pada 1972, Reducibilitas Diantara Masalah Combinatorial , Karp membuktikan bahwa SAT berkurang menjadi 3SAT dengan menyatakan:

Ganti klausa , di mana adalah literal dan , dengan mana adalah variabel baru. Ulangi transformasi ini hingga tidak ada klausa yang memiliki lebih dari tiga literal. $\sigma_1 \cup \sigma_2 \cup \ldots \cup \sigma_m$ $\sigma_i$ $m>3$
$(σ_{1} \cup σ_{2} \cup u_{1}) (σ_{3} \cup \dots \cup σ_{m} \cup {\bar{u}}_{1}) ({\bar{σ}}_{3} \cup u_{1}) \dots ({\bar{σ}}_{m} \cup u_{1}),$ $(\sigma_1 \cup \sigma_2 \cup u_1) (\sigma_3 \cup \ldots \cup \sigma_m \cup \bar{u}_1) (\bar{\sigma}_3 \cup u_1) \ldots (\bar{\sigma}_m \cup u_1),$ $u_1$

Sepertinya saya bahwa klausa (yaitu klausa yang mengandung dua literal) di sini tidak perlu. Jadi, konstruksinya benar seperti tertulis tetapi lebih rumit dari yang diperlukan. Tanpa klausa 2-literal, kami memperoleh konstruksi yang biasanya diberikan dalam buku teks sarjana. Apakah ini benar, atau saya kehilangan sesuatu yang jelas? Saya merasa sangat tidak yakin pada diri saya menyarankan bahwa apa pun yang dilakukan oleh Karp dapat diekspresikan lebih elegan. $m-2$

cc.complexity-theory sat reductions John MacCormick
sumber

Jawaban:

dari dua klausa pertama, sesuai dengan klausa asli, karena dapat dengan mudah diperiksa (setiap penilaian yang memenuhi salah satu dari juga memenuhi salah satu dari dua klausa baru, dan dapat diperluas ke sesuai kebutuhan untuk memenuhi yang lain; penilaian apa pun yang memenuhi kedua klausa baru harus memenuhi beberapa , karena tidak dapat memenuhi keduanya dan .) $(\sigma_1\cup\sigma_2\cup u_1)(\sigma_3\cup\ldots\cup\sigma_m\cup\bar{u}_1)$ $\sigma_i$ $u_1$ $\sigma_i$ $u_1$ $\bar{u}_1$

Klausa tambahan memastikan bahwa sebenarnya setara dengan , tetapi sejauh yang saya bisa lihat, Karp sebenarnya tidak menggunakan ini. Dia memuji makalah Cook tahun 1971 untuk pengurangan khusus ini, tetapi versi yang ditemukan di sana (sebenarnya untuk tautologi DNF dan bukan kepuasan CNF) tidak menonjolkan kendala-kendala tambahan ini. $u_1$ $\sigma_3\cup\ldots\cup\sigma_m$

Klaus Draeger
sumber

Terima kasih atas jawabannya. Mengulangi untuk memperkuat dan memeriksa pemahaman saya, cara lain untuk menyatakan ini adalah bahwa klausa tambahan memastikan ini adalah pengurangan dari #SAT ke # 3SAT (karena mereka mempertahankan jumlah solusi dan bukan hanya keberadaan solusi).

John MacCormick