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ý.
Příslušnost do NP. Problém FAIR-SAT 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 ϕ, která má sudý počet výrokových proměnných (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 ϕ tak, aby právě polovina proměnných měla hodnotu true a polovina hodnotu
false (lineární čas vzhledem k počtu proměnných, tedy i vzhledem k velikosti formule). Následně
stroj vyhodnotí, zda je formule ϕ touto valuací splněná. 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.
NP-těžkost. Ukážeme, že SAT ≤p FAIR-SAT. Uvažme funkci f, která je pro vstupní řetězec w
definována takto: pokud w není kódem výrokové formule, pak f(w) = w. V opačném případě označme
ϕ výrokovou formuli zakódovanou řetězcem w a dále nechť n značí počet výrokových proměnných
ve ϕ. Definujeme
f(w) = ϕ ∧ ψ , kde ψ = (x1 ∨ ¬x1) ∧ (x2 ∨ ¬x2) ∧ . . . ∧ (xn ∨ ¬xn)
a x1, . . . , xn jsou proměnné, které se nevyskytují ve ϕ. Všimněme si, že formule zakódovaná v f(w)
má 2n proměnných a její část ψ je splněná každou valuací proměnných. Funkce f je vyčíslitelná
deterministickým strojem s polynomiální časovou složitostí: stroj nejprve zkontroluje, zda vstup je
kódem formule, a pokud ano, spočítá výrokové proměnné ve ϕ, vygeneruje formuli ψ, jejíž velikost
je O(|ϕ|), a na výstup dá zakódovanou konjunkci ϕ ∧ ψ.
Zbývá ukázat, že w ∈ SAT ⇔ f(w) ∈ FAIR-SAT. Tato ekvivalence zřejmě platí pro w, která
nejsou kódy výrokových formulí, protože pak w ∈ SAT a f(w) = w ∈ FAIR-SAT. Ve zbytku
důkazu tedy předpokládejme, že w = ϕ , kde ϕ je výroková formule, a označme n počet výrokových
proměnných ve ϕ.
“⇒” Nechť ϕ ∈ SAT, tedy existuje valuace ν splňující ϕ. Nechť m ≤ n je počet proměnných z ϕ,
které tato valuace zobrazí na true. Nyní zadefinujeme valuaci ν takto: pro každou proměnnou
y, která se vyskytuje ve ϕ, položíme ν (y) = ν(y) a dále pak ν (x1) = ν (x2) = . . . =
ν (xm) = false a ν (xm+1) = . . . = ν (xn) = true. Valuace ν splňuje formuli ϕ ∧ ψ a zobrazuje
právě m + (n − m) = n proměnných z této formule na true a zbývajících n proměnných na
false. Tedy f( ϕ ) = ϕ ∧ ψ ∈ FAIR-SAT.
“⇐” Nechť f( ϕ ) = ϕ ∧ ψ ∈ FAIR-SAT. Pak existuje valuace, která (mimo další požadavky)
splňuje formuli ϕ ∧ ψ. Z toho okamžitě plyne, že formule ϕ je splnitelná. Tedy ϕ ∈ SAT.
Oblast strojově snímaných informací, nezasahujte. Zde jsou losi.