IB107 úkol 3, příklad 2 Odevzdání: 7. 12. 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. [3 body] Uvažme problém pro danou gramatiku G typu 0 (tedy bez omezení) a dané k ∈ N
rozhodnout, zda lze v této gramatice odvodit prázdné slovo ε v nejvýše k krocích. Problém nazveme
bounded epsilon derivation a ztotožníme s množinou
BED = { G, k | G je gramatika splňující S
≤k
=⇒G ε, kde S je kořenem G}.
Dokažte, že problém BED je NP-těžký.
NP-těžkost problému BED dokážeme redukcí z problému 3SAT, tedy redukcí 3SAT ≤p BED.
Redukční funkce f(w) je definovaná následovně. Není-li w kódem výrokové formule v 3CNF, pak
klademe f(w) = G0, 1 , kde G0 = ({S}, {a}, {S → a}, S) je gramatika, ve které nelze odvodit ε.
Ekvivalence w ∈ 3SAT ⇐⇒ f(w) ∈ BED pro tato w jistě platí, neboť w ∈ 3SAT a f(w) ∈ BED.
Nyní se zaměříme na případ, kdy w = ϕ pro nějakou formuli ϕ v 3CNF. Nechť n je počet
klauzulí ve ϕ a X1, . . . , Xp jsou výrokové proměnné, které se vyskytují ve ϕ. Jistě platí p ≤ |ϕ|. Nyní
uvažme následující gramatiku G = (N, Σ, P, S):
• N = {S, T, F} ∪ {Xi, X?
i , XT
i , XF
i | 1 ≤ i ≤ p}, kde T, F reprezentují pravdivostní hodnoty
true, false a pro každou výrokovou proměnnou máme neterminál Xi pro zápis této proměnné
ve formuli, neterminál X?
i sloužící k nedeterministickému výběru valuace této proměnné a
neterminály XT
i , XF
i značící, že proměnné Xi byla přiřazena hodnota true, resp. false
• Σ = {∧, ∨, ¬, (, )}
• P = P1 ∪ P2 ∪ P3 ∪ P4 ∪ P5 ∪ P6, kde
– Pravidlo přepisující S na ϕ (zapsanou pomocí znaků z N ∪ Σ) a řetězec neterminálů
sloužících k nedeterministickému výběru valuace:
P1 = {S → ϕX?
1X?
2 . . . X?
p}
– Pravidla pro nedeterministický výběr valuace:
P2 = {X?
i → XT
i , X?
i → XF
i | 1 ≤ i ≤ p}
– Pravidla umožňující neterminálům XT
i , XF
i “projet” doleva přes celou větnou formu, každý
výskyt proměnné Xi ve formuli přepsat na T nebo F dle zvolené valuace a následně se
přepsat na ε:
P3 = {AXT
i → XT
i A, AXF
i → XF
i A | 1 ≤ i ≤ p, A ∈ (N ∪ Σ) {Xi}} ∪
{XiXT
i → XT
i T, XiXF
i → XF
i F | 1 ≤ i ≤ p} ∪
{XT
i → ε, XF
i → ε | 1 ≤ i ≤ p}
– Pravidla umožnující vyhodnotit negované literály:
P4 = {¬T → F, ¬F → T}
– Pravidla umožnující přepsat na T každou klauzuli s alespoň jedním literálem vyhodnoceným
na T:
P5 = {(T ∨ T ∨ T) → T, (T ∨ T ∨ F) → T, (T ∨ F ∨ T) → T,
(T ∨ F ∨ F) → T, (F ∨ T ∨ T) → T, (F ∨ T ∨ F) → T, (F ∨ F ∨ T) → T}
Oblast strojově snímaných informací, nezasahujte. Zde jsou losi.
IB107 úkol 3, příklad 2 Odevzdání: 7. 12. 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.
– Pravidla umožnující přepsat libovolnou sekvenci tvaru T ∧ T ∧ . . . ∧ T na ε:
P6 = {T ∧ T → T, T → ε}
Pravidla z P1 ∪ P2 umožnují v p + 1 krocích přepsat počáteční neterminál S na řetězec ϕα, kde
α ∈ {XT
1 , XF
1 }.{XT
2 , XF
2 } . . . {XT
p , XF
p } jednoznačně určuje valuaci proměnných. Každý neterminál
XT
i , XF
i pak může pomocí pravidel z P3 v nejvýše |ϕ| + 1 krocích “projet” doleva přes celou formuli,
přepsat výskyty Xi na odpovídající hodnotu T nebo F a zmizet. Tato fáze zabere nejvýše p·(|ϕ| + 1)
kroků. Pravidla v P4, P5, P6 následně umožňují vyhodnotit negace, splněné klauzule přepsat na T a
konjunkci libovolně mnoha T přepsat na ε, to vše v nejvýše |ϕ| krocích. Je tedy zřejmé, že pokud
existuje valuace splňující ϕ, pak lze v gramatice G odvodit ε v nejvýše (|ϕ|+1)+p·(|ϕ|+1)+|ϕ| ≤
|ϕ|2 + 3|ϕ| + 1 krocích.
Nyní předpokládejme, že v G lze odvodit ε. Jediným pravidlem pro S je pravidlo z P1, po jehož
aplikaci se do větné formy dostane n řetězců tvaru {(}.(N ∪ {∨, ¬})+.{)} (jeden pro každou klauzuli
formule ϕ). Jelikož závorky lze odstranit jen pomocí pravidel z P5, musel se každý řetězec výše
uvedeného tvaru přepsat na řetězec tvaru (V1 ∨ V2 ∨ V3), kde V1, V2, V3 ∈ {T, F} a aspoň jedno
z V1, V2, V3 je T. To však mohlo nastat jen po aplikaci p pravidel z P2 a dalších pravidel z P3 a P4.
Aplikovaná pravidla z P2 pak kódují valuaci, která je splňující pro ϕ.
Tím jsme dokázali, že platí
ϕ ∈ 3SAT ⇐⇒ G, |ϕ|2
+ 3|ϕ| + 1 ∈ BED.
Pokud tedy definujeme f( ϕ ) = G, |ϕ|2 + 3|ϕ| + 1 , vidíme, že ekvivalence w ∈ 3SAT ⇐⇒ f(w) ∈
BED je splněna pro všechna slova w, která jsou kódem nějaké formule v 3CNF, a dohromady
s úvodním odstavcem tak dostáváme, že je tato ekvivalence splněna pro všechna slova w.
Zbývá dokázat, že funkce f je vyčíslitelná deterministickým strojem v polynomiálním čase. Rozhodnout,
zda vstupní slovo w je kódem nějaké formule ϕ v 3CNF, a zkonstruovat gramatiku G0 jistě
lze deterministicky v polynomiálním čase. Nyní zanalyzujeme gramatiku G konstruovanou v případě,
že w = ϕ : Množina N je velikosti O(p), abeceda Σ je konstantní. Délka pravidla v P1 je O(|ϕ|+p)
a množiny P2, . . . , P6 obsahují pouze pravidla konstantních délek, kterých je O(p) v případě P2,
O(p2) v případě P3 a konstantní počet v případě P4, P5, P6. Jelikož p ≤ |ϕ|, je velikost konstruované
gramatiky v O(|ϕ|2). Její konstrukce je přitom přímočará.
Oblast strojově snímaných informací, nezasahujte. Zde jsou losi.