Bagaimana cara membuktikan bahwa versi 3SAT yang terbatas di mana tidak ada literal yang dapat muncul lebih dari sekali, dapat dipecahkan dalam waktu polinomial?

Saya mencoba mengerjakan tugas (diambil dari buku Algoritma - oleh S. Dasgupta, CH Papadimitriou, dan UV Vazirani , Bab 8, masalah 8.6a), dan saya memparafrasekan apa yang dinyatakannya:

Mengingat bahwa 3SAT tetap NP-lengkap bahkan ketika terbatas pada rumus di mana setiap literal muncul paling banyak dua kali, menunjukkan bahwa jika setiap literal muncul paling banyak satu kali, maka masalahnya dapat dipecahkan dalam waktu polinomial.

Saya mencoba menyelesaikan ini dengan memisahkan klausa menjadi beberapa kelompok:

1. Klausa yang tidak memiliki variabel apa pun yang sama dengan klausa lainnya
2. Klausa yang hanya memiliki 1 variabel
3. Klausa yang memiliki 2 variabel yang sama
4. Klausa yang memiliki ketiga variabel secara umum

Alasan saya dicoba di sepanjang baris bahwa # dari kelompok tersebut adalah terbatas (karena pembatasan yang diberlakukan tidak ada literal hadir lebih dari satu kali), dan kami dapat mencoba untuk memuaskan kelompok yang paling terbatas terlebih dahulu (kelompok 4) dan kemudian mengganti menghasilkan kelompok terbatas yang lebih rendah (3, 2 dan kemudian 1), tetapi saya menyadari bahwa ini tidak cukup membuat saya ke mana pun, karena ini tidak berbeda jauh dari kasus untuk versi 3SAT yang dibatasi di mana setiap literal dapat muncul paling banyak dua kali, yang telah terbukti sebagai NP-complete.

Saya mencoba mencari petunjuk / solusi secara daring, tetapi yang bisa saya dapatkan hanyalah tautan ini , di mana petunjuk yang disebutkan tidak masuk akal bagi saya, yang saya buat ulang di sini:

Petunjuk: Karena setiap literal muncul paling banyak sekali, konversikan masalah ini menjadi masalah 2SAT - maka waktu polinomial, jika literal muncul dalam klausa dan komplemen dari (yaitu, ) dalam klausa , buat klausa baru klausa .$x_i$$C_j$$x_i$$\overline{x_i}$$C_k$$C_j \lor \overline{C_k}$

Baik dan masing-masing memiliki tiga literal - Saya tidak mengerti bagaimana saya harus mengubahnya menjadi 2SAT dengan melakukan (atau jika saya membacanya dengan salah).$C_j$$C_k$$C_j \lor \overline{C_k}$$\overline{C_j \lor C_k}$

Setiap bantuan dalam mendekripsi petunjuk, atau menyediakan jalur yang dapat saya jelajahi akan sangat dihargai.

Tanpa kehilangan generalitas, kita dapat mengasumsikan bahwa setiap variabel muncul tepat sekali positif dan tepat sekali negatif (jika variabel hanya muncul satu kali, setel nilainya untuk memenuhi klausa dan menghapus klausa). Kita juga dapat mengasumsikan bahwa suatu variabel tidak muncul dalam suatu klausa lebih dari sekali (jika suatu variabel muncul secara positif dan negatif dalam suatu klausa, maka klausa tersebut terpenuhi dan dapat dihapus). Ini tidak akan mengubah kepuasan.

Sekarang gunakan aturan resolusi untuk menghilangkan variabel satu per satu (karena setiap variabel muncul tepat sekali positif dan sekali negatif ini adalah proses deterministik). Jika pada suatu saat kita mendapatkan klausa kosong, klausa tidak memuaskan, jika tidak, klausa tersebut memuaskan. Hal ini karena:

• resolusi adalah sistem bukti proposisional lengkap (yaitu jika suatu klausa secara logis tersirat oleh himpunan klausa maka itu dapat diturunkan dari himpunan klausa hanya menggunakan aturan resolusi),

• satu set klausa tidak memuaskan jika secara logis menyiratkan klausa kosong.

Algoritma ini akan memakan waktu polinomial karena setiap variabel diselesaikan tepat sekali. Secara khusus, setiap penerapan resolusi akan mengurangi jumlah klausa per satu, sehingga jumlah klausa tidak bertambah. Misalnya, menerapkan resolusi ke menghasilkan , yang memiliki satu klausa lebih sedikit daripada sebelum resolusi. Sebaliknya, jika Anda menerapkan ini pada rumus 3SAT tanpa batasan pada jumlah penampilan setiap literal, menerapkan resolusi dapat menyebabkan jumlah klausa meningkat secara eksponensial.$(x \lor B) \land (\overline{x} \lor C) \land \dots)$$(B \lor C) \land \dots$