Buktikan NP-kelengkapan memutuskan kepuasan formula monoton boolean

Saya mencoba menyelesaikan masalah ini dan saya benar-benar berjuang.

Sebuah monoton rumus boolean adalah formula dalam logika proposisional mana semua literal positif. Sebagai contoh,

$\qquad (x_1 \lor x_2) \land (x_1 \lor x_3) \land (x_3 \lor x_4 \lor x_5)$

adalah fungsi boolean monoton. Di sisi lain, sesuatu seperti

$\qquad (x_1 \lor x_2 \lor x_3) \land (\neg x_1 \lor x_3) \land (\neg x_1 \lor x_5)$

bukan fungsi boolean monoton.

Bagaimana saya bisa membuktikan kelengkapan NP untuk masalah ini:

Tentukan apakah fungsi boolean monoton memuaskan jika variabel atau kurang ditetapkan ke 1 ?$k$$1$

Jelas, semua variabel bisa saja ditetapkan menjadi positif, dan itu sepele, jadi itu sebabnya ada pengekangan variabel set positif .$k$

$\neg x_1$$z_1$$x_1$$z_1$

$k$

Pembatasan terhadap formula monoton ternyata sangat mudah untuk menunjukkan kekerasan, Anda hanya perlu menyelesaikan masalah di luar kepuasan sejenak. Alih-alih mencoba memodifikasi instance SAT, kami malah mulai dengan Dominating Set (DS).

Lihat apakah Anda bisa mendapatkannya dari sana. Lebih banyak ada di spoiler, dipecah menjadi bit, tetapi hindari jika Anda bisa. Saya tidak akan menunjukkan keanggotaan di NP, Anda seharusnya tidak memiliki masalah dengan itu.

$(G, k)$$k$$G$$(\phi,k)$$\phi$

Konstruksi dasar:

$v\in V(G)$$v' \in \text{var}(\phi)$$v \in V(G)$$c_{v} = \bigvee_{u\in N(v)} u'$

Sebuah sketsa bukti:

$k$$k$$\phi$$k$$c_{v}$$v$

$z_i$$\neg x_i$$\phi$$\phi'$$\neg x_i$$z_i$$x_i \vee z_i$$k$$\phi'$$\phi$$k$$x_i \vee z_i$$\phi'$$k$$k$