IB107 úkol 3, příklad 1 Odevzdání: 8. 12. 2023, 23:59
Jméno: Nesmlouvavý Pstruh UČO: 1234567
list učo body
Oblast strojově snímaných informací. Své učo a číslo listu vyplňte
zleva dle vzoru číslic. Jinak do této oblasti nezasahujte.
1. [3 body] Řekneme, že výroková formule ϕ v konjunktivní normální formě (CNF) je napůl
splnitelná, právě když existuje valuace splňující přesně n
2 klauzulí formule ϕ, kde n je počet klauzulí
této formule.
Uvažme problém rozhodnout, zda je daná výroková formule v CNF napůl splnitelná, tedy problém
HALFSAT = { ϕ | ϕ je formule v CNF, která je napůl splnitelná}.
Dokažte, že HALFSAT je NP-úplný.
Oblast strojově snímaných informací, nezasahujte. Zde jsou losi.