IB107 úkol 3, příklad 1 Odevzdání: 7. 12. 2021, 23:59
Jméno: Nemotorný Ptakopysk 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 ϕ je férově splnitelná, pokud se v ní vyskytuje sudý
počet výrokových proměnných a je splněná nějakou valuací těchto proměnných, ve které má polovina
proměnných hodnotu true a druhá polovina hodnotu false.
Uvažme problém rozhodnout, zda je daná výroková formule férově splnitelná, tedy problém
FAIR-SAT = { ϕ | ϕ je férově splnitelná}.
Dokažte, že FAIR-SAT je NP-úplný.
Oblast strojově snímaných informací, nezasahujte. Zde jsou losi.