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ý. Příslušnost do NP. Problém STRONGSAT 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 jsou v této valuaci pravdivé v každé klauzuli alespoň 2 různé literály (to lze udělat v jednom průchodu přes 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ě STRONGSAT. NP-těžkost. Ukážeme, že 3SAT ≤p STRONGSAT. Uvažme funkci f definovanou vztahem f(x) =    y ∧ ¬y pokud x není kódem formule v 3CNF, ϕ pokud x = ϕ a ϕ je v 3CNF, kde ϕ vznikne z ϕ přidáním literálu z do každé klauzule, přičemž z je výroková proměnná, která se nevyskytuje ve ϕ. 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 ∧ ¬y . Pokud je, přidá do každé její klauzule literál z a na výstup dá výslednou zakódovanou formuli. Zbývá ukázat, že x ∈ 3SAT ⇐⇒ f(x) ∈ STRONGSAT. 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 ∧ ¬y ∈ STRONGSAT. Ve zbytku důkazu tedy předpokládejme, že x = ϕ , kde ϕ je výroková formule v 3CNF. “=⇒” Nechť ϕ ∈ 3SAT, tedy existuje valuace ν splňující ϕ. Jinými slovy, v každé klauzuli formule ϕ je literál, který je ve valuaci ν pravdivý. Nyní uvažme valuaci ν , která se na proměnných z ϕ chová stejně jako ν a proměnnou z zobrazí na true. Ve valuaci ν jsou v každé klauzuli formule ϕ pravdivé alespoň dva literály: původní literál pravdivý ve valuaci ν a přidaný literál z. Tyto literály jsou vždy různé, protože z je čerstvá proměnná. Tedy f( ϕ ) = ϕ ∈ STRONGSAT “⇐=” Nechť f( ϕ ) = ϕ ∈ STRONGSAT, tedy existuje valuace ν, ve které jsou v každé klauzuli formule ϕ pravdivé alespoň dva různé literály. Jelikož jsme při konstrukci ϕ do každé klauzule přidali pouze jeden literál, musí být alespoň jeden z literálů pravdivých ve valuaci ν zároveň literálem v odpovídající klauzuli původní formule ϕ. Stejná valuace tedy splňuje původní formuli ϕ a proto ϕ ∈ 3SAT. Oblast strojově snímaných informací, nezasahujte. Zde jsou losi.