Kompleksitas dari masalah SAT?

Mari tentukan masalah SAT: Diberikan , rumus 3-CNF yang memuaskan, dan , rumus 2-CNF ( dan didefinisikan pada variabel yang sama). Apakah memuaskan?$(3,2)_s$$F_3$$F_2$$F_3$$F_2$$F_3 \wedge F_2$

Apa kompleksitas masalah ini? (Apakah sudah dipelajari sebelumnya?)

Masalah ini sudah selesai NP.

Biarkan menjadi rumus CNF yang berubah-ubah (turunan dari SAT). Pertimbangkan φ ∨ y , di mana y adalah variabel baru; jelas, rumus ini memuaskan (Anda dapat mengatur y menjadi true). Sekarang konversikan φ ∨ y ke 3-CNF, menggunakan metode standar apa pun, dan biarkan ψ menunjukkan hasilnya. Perhatikan bahwa ψ adalah formula 3-CNF yang memuaskan, sehingga kita dapat membiarkan F 3 = ψ . Sekarang, biarkan F 2 = ¬ y . Perhatikan bahwa F 3 ∧ F 2 memuaskan jika dan hanya jika$\varphi$$\varphi \lor y$$y$$y$$\varphi \lor y$$\psi$$\psi$$F_3 = \psi$$F_2 = \neg y$$F_3 \land F_2$ adalah. Oleh karena itu, ( 3 , 2 ) s masalah SAT setidaknya sekeras SAT. Juga, jelas tidak lebih sulit daripada SAT. Karena itu, sama sulitnya dengan SAT.$\varphi$$(3,2)_s$

Berikut ini adalah makalah dari Porshen dan Speckenmayer: Kepuasan formula Horn campuran yang menunjukkan bahwa bahkan ketika adalah Horn, masalah menentukan kepuasan F 3 ∧ F 2 adalah NP-complete.$F_3$$F_3 \wedge F_2$