IB107 úkol 3, příklad 1 Odevzdání: 9. 12. 2022, 23:59
Jméno: Nesmělý Panter 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ě je silně splnitelná,
pokud existuje valuace proměnných, ve které jsou pravdivé alespoň dva různé literály z každé klauzule
(dva výskyty téhož literálu v jedné klauzuli nepovažujeme za různé literály).
Uvažme problém rozhodnout, zda je daná výroková formule v CNF silně splnitelná, tedy problém
STRONGSAT = { ϕ | ϕ je formule v CNF, která je silně splnitelná}.
Dokažte, že STRONGSAT je NP-úplný.
Oblast strojově snímaných informací, nezasahujte. Zde jsou losi.