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ý. Příslušnost do NP. Problém HALFSAT je rozhodován např. nedeterministickým Turingovým strojem, který pracuje následovně: stroj nejprve deterministicky ověří, zda vstup je kódem nějaké výrokové formule ϕ v CNF (to lze jistě učinit v polynomiálním čase). Pokud tomu tak není, ihned zamítne. V opačném případě nedeterministicky vybere nějakou valuaci proměnných z ϕ a vyhodnotí, zda tato valuace splňuje právě n 2 klauzulí, kde n je počet klauzulí ve formuli ϕ. Pokud ano, stroj akceptuje, jinak zamítá. Všechny uvedené operace lze na Turingově stroji implementovat v polynomiálním čase, tedy uvedený stroj má polynomiální časovou složitost. Je zjevné, že tento Turingův stroj akceptuje právě HALFSAT. NP-těžkost. Ukážeme, že 3SAT ≤p HALFSAT, kde 3SAT je známý NP-těžký problém. Uvažme funkci f definovanou vztahem f(x) =    ¬(y ∧ z) pokud x není kódem formule v 3CNF, ϕ pokud x = ϕ a ϕ je formule v 3CNF s klauzulemi c1, c2, . . . , cn, kde ϕ = c1 ∧ c2 ∧ . . . ∧ cn ∧ z1 ∧ z2 ∧ . . . ∧ zn je formule s 2n klauzulemi, každá klauzule ci je tvaru ci = ci∨z1∨z2∨. . .∨zn a z1, z2, . . . zn jsou čerstvé výrokové proměnné. Funkce f je totálně vyčíslitelná deterministickým strojem s polynomiální časovou složitostí, který funguje následovně. Stroj nejprve zkontroluje, zda vstup je kódem formule v 3CNF. Pokud není, zapíše na pásku ¬(y ∧ z) . Pokud je, přidá do každé její klauzule literály z1, . . . , zn a dále k formuli přidá dalších n klauzulí z1 ∧ . . . ∧ zn a na výstup dá výslednou zakódovanou formuli. Zbývá ukázat, že x ∈ 3SAT ⇐⇒ f(x) ∈ HALFSAT. Tato ekvivalence zřejmě platí pro x, která nejsou kódy výrokových formulí v 3CNF, protože pak x ∈ 3SAT a f(x) = ¬(y ∧ z) ∈ HALFSAT, neboť ¬(y ∧ z) není formule v CNF. Ve zbytku důkazu tedy předpokládejme, že x = ϕ , kde ϕ je výroková formule v 3CNF s klauzulemi c1, c2, . . . , cn. “=⇒” Nechť ϕ ∈ 3SAT, tedy existuje valuace ν splňující ϕ. Jinými slovy, všechny klauzule c1, . . . , cn jsou pravdivé ve valuaci ν. Nyní uvažme valuaci ν , která se na proměnných z ϕ chová stejně jako ν a proměnné z1, . . . , zn zobrazí na false. Ve valuaci ν jsou pravdivé klauzule c1, . . . , cn a naopak nejsou pravdivé klauzule z1, . . . , zn. Celkem je tedy valuací ν splněno právě n = 2n 2 z 2n klauzulí formule ϕ a proto f( ϕ ) = ϕ ∈ HALFSAT “⇐=” Nechť f( ϕ ) = ϕ ∈ HALFSAT, tedy existuje valuace ν splňující právě n klazulí z ϕ . Tato valuace musí zobrazovat všechny proměnné z1, . . . , zn na false, protože každý literál zi je v n+1 klazulích a tudíž zobrazení, které by nějaké zi zobrazilo na true, by splnilo více než n klauzulí. Zobrazení ν tedy nesplňuje klauzule z1, . . . , zn a tudíž musí splnit klauzule c1, . . . , cn. Jelikož každá klazule ci má tvar ci ∨ z1 ∨ z2 ∨ . . . ∨ zn, musí ν splnit i všechny klauzule ci z ϕ a tato formule v 3CNF je tedy splnitelná. Proto ϕ ∈ 3SAT. Oblast strojově snímaných informací, nezasahujte. Zde jsou losi.