IB107 úkol 3, příklad 2 Odevzdání: 7. 1. 2021, 23:59 Jméno: Noblesní Plšice 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. 2. [2,5 bodu] Nechť A je deterministický konečný automat (DFA) se vstupní abecedou Σ (připomeňme, že Σ je dána jakožto součást n-tice popisující A). Řekneme, že A je znakově univerzální pokud existuje slovo w ∈ Σ∗ splňující tyto 3 podmínky: • w je akceptováno automatem A • délka w je menší nebo rovna počtu stavů automatu A • každý znak abecedy Σ se ve w vyskytuje alespoň jednou (formálně, s využitím značení z FJA/Automatů: ∀a ∈ Σ : #a(w) ≥ 1). Dokažte, že problém CHAR-UNIV = { A | A je znakově univerzální DFA Σ} je NP-úplný. Příslušnost do NP. Problém CHAR-UNIV je rozhodován např. nedeterministickým Turingovým strojem, který pracuje následovně. Stroj nejprve deterministicky ověří, zda vstup je kódem nějakého DFA A (to lze jistě učinit v polynomiálním čase). Pokud tomu tak není, ihned zamítne. V opačném případě uhádne nějaké slovo w délky nejvýše n (kde n je počet stavů automatu A) nad abecedou Σ automatu A. Následně deterministicky ověří, zda w obsahuje každé písmeno abecedy Σ. Pokud tomu tak není, stroj ihned zamítne. V opačném případě stroj deterministicky odsimuluje výpočet A nad w a ověří, že tento výpočet končí v akceptujícím stavu (pokud ano, pak stroj akceptuje, jinak zamítne). Všechny uvedené výpočty jsou proveditelné nedeterministickýcm Turingovým strojem, který běží v polynomiálním čase. NP-těžkost. Ukážeme, že 3-SAT ≤p CHAR-UNIV. Redukci f definujeme jako f(w) = A∅ pokud w není kódem výrokové formule v 3cnf, Aϕ pokud w je kódem výrokové formule ϕ v 3cnf, kde A∅ je nějaký fixní DFA bez akceptujících stavů a Aϕ je DFA zkonstruovaný v závislosti na výrokové formuli ϕ v 3cnf následovně. Nechť ϕ = C1 ∧. . .∧Cm (C1, . . . , Cm jsou klauzule ϕ) a nechť ϕ obsahuje výrokové proměnné x1, . . . , xn. Automat Aϕ = (Qϕ, Σϕ, δϕ, q0, Fϕ) konstruujeme takto: • Do množiny stavů Qϕ nejprve přidáme stavy q0, q0, q1, q2, . . . , qn+1. Další stavy budeme do Qϕ přidávat v průběhu konstrukce. • Položíme Σϕ = {1, . . . , m, t, f}, tedy máme jeden znak pro každou klauzuli, který odpovídá číslu klauzule, a dále pomocné znaky t a f. • Automat má jediný koncový stav F = {qn+1}. • Zbývá definovat přechodovou funkci. V následujícím budeme psát p a → q namísto δϕ(p, a) = q a tento zápis přechodů budeme pro větší přehlednost řetězit. Stavy q0, q0 mají po jednom přechodu: q0 t → q0 f → q1. Pro každou výrokovou proměnnou xi provedeme následující: – Vypočteme množiny pos(i) = {j | 1 ≤ j ≤ m a Cj obsahuje literál xi} a neg(i) = {j | 1 ≤ j ≤ m a Cj obsahuje literál ¬xi}. – Označme k = |pos(i)|. Pokud k = 0, přidáme přechod qi t → qi+1. Oblast strojově snímaných informací, nezasahujte. Zde jsou losi. IB107 úkol 3, příklad 2 Odevzdání: 7. 1. 2021, 23:59 Jméno: Noblesní Plšice 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. – Pokud k > 0, můžeme psát pos(i) = {j1, . . . , jk}. Přidáme do Qϕ nové stavy p1 i , p2 i , . . . , pk i a definujeme přechody qi t → p1 i j1 → p2 i j2 → . . . jk−1 → pk i jk → qi+1. Tedy vytvoříme v Aϕ „cestu“ z qi do qi+1, přičemž na této cestě Aϕ čte symbol t a následně symboly, které odpovídají klauzulím obsahujícím xi. – Označme = |neg(i)|. Pokud = 0, přidáme přechod qi f → qi+1. – Pokud > 0, můžeme psát neg(i) = {j1, . . . , j }. Přidáme do Qϕ nové stavy s1 i , s2 i , . . . , si a definujeme přechody qi f → s1 i j1 → s2 i j2 → . . . j −1 → si j → qi+1. Tedy vytvoříme v Aϕ „cestu“ z qi do qi+1, přičemž na této cestě Aϕ čte symbol f a následně symboly, které odpovídají klauzulím obsahujícím ¬xi. Snadno lze ověřit, že výše uvedená konstrukce skutečně vytvoří DFA. Navíc snadno vytvoříme program s polynomiální časovou složitostí (O(m·n)), který ji provádí, a tento program lze implementovat deterministickým Turingovým strojem s polynomiální časovou složitostí. Zbývá tedy ukázat, že w ∈ 3-SAT ⇐⇒ f(w) ∈ CHAR-UNIV. Tato ekvivalence zřejmě platí pro w, která nejsou kódy 3cnf formulí. Ve zbytku důkazu tedy předpokládejme, že w = ϕ , kde ϕ je formule v 3cnf. Před samotným důkazem učiňme následující pozorování: slova akceptovaná automatem Aϕ jsou právě slova tvaru tfy1u1 · · · ynun, kde yi ∈ {t, f} a kde složení podslov ui je dáno tím, zda yi = t či yi = f. V prvním případě je ui tvořeno právě znaky z pos(i), ve druhém případě je ui tvořeno právě znaky z neg(i). (Všimněme si, že ui mohou být prázdná.) Navíc zřejmě každé slovo akceptované tímto automatem má délku menší, než je počet stavů tohoto automatu. “⇒” Nechť w = ϕ ∈ 3-SAT. Pak existuje přiřazení ν proměnným ve ϕ takové, že ν(ϕ) = true. Uvažme slovo u = tfy1u1 · · · ynun takové, že yi = t pokud ν(xi) = true a yi = f pokud ν(xi) = false. Podslova u1, . . . , un jsou dána předpisem výše. Protože ν je splňující přiřazení, každá klauzule Cj obsahuje literál vyhodnocený na true. Pokud je tento literál tvaru xi pro nějaké i, pak j ∈ pos(i). Zároveň ν(xi) = true a tedy ui (a tudíž i u) obsahuje všechny znaky z pos(i), včetně j. Podobně pokud je splněný literál v Cj tvaru ¬xi pro nějaké i, pak j ∈ neg(i) a zároveň ν(xi) = false, tedy ui (a u) obsahují j. Protože Cj bylo zvoleno libovolně, dostáváme že u obsahuje všechna 1 ≤ j ≤ m. Zřejmě též u obsahuje t a f a je akceptováno automatem Aϕ. Tedy f(w) = Aϕ ∈ CHAR-UNIV. “⇐” Nechť u je slovo akceptované automatem Aϕ, které obsahuje každý znak abecedy alespoň jednou. Z výše uvedeného plyne, že u = tfy1u1 · · · ynun kde yi ∈ {t, f}. Uvažme přiřazení ν takové, že pro 1 ≤ i ≤ n je ν(xi) = true pokud yi = t, jinak ν(xi) = false. Ukážeme, že ν(ϕ) = true. Nechť Cj je libovolná klauzule ϕ. Víme, že znak j se vyskytuje někde v u. Existuje tedy 1 ≤ i ≤ n takové, že ui obsahuje j. Pokud yi = t, pak ui obsahuje právě znaky z pos(i) a tedy xi ∈ Cj; zároveň z definice ν je ν(xi) = true, tedy Cj je splněna. Podobně pokud yi = f, pak ui obsahuje právě znaky z neg(i) a tedy ¬xi ∈ Cj; zároveň z definice ν je ν(xi) = false a tedy ν(¬xi) = true. I v tomto případě je tedy Cj je splněna. Jelikož ν splňuje všechny klauzule z ϕ, je ϕ splnitelná a w = ϕ ∈ 3-SAT. Oblast strojově snímaných informací, nezasahujte. Zde jsou losi.