IB102 – úkol 11, příklad 2 – řešení Odevzdání: 16. 12. 2013
Vypracoval(a): UČO:
Skupina:
2. [2 body]
(a) Připomeňme definici třídy coNP:
coNP = {co−L | L ∈ NP}.
Dokažte, že platí inkluze P ⊆ NP ∩ coNP. Tedy ukažte, že každý jazyk L ∈ P splňuje
L ∈ NP a zároveň L ∈ coNP.
(b) Neformálně zdůvodněte, proč každý regulární jazyk R splňuje R ∈ TIME(n). Tedy
vysvětlete, proč pro každý regulární jazyk existuje Turingův stroj, který ho rozhoduje,
a navíc má lineární časovou složitost vzhledem k délce vstupního slova.
Bonus: [+1 bod] Úlohu (b) dokažte formálně. Přesně popište převod konečného deterministického
automatu na jazykově ekvivalentní Turingův stroj. Zdůvodněte, proč má
Turingův stroj, který vznikne touto konstrukcí, lineární časovou složitost.
(a) Nejprve dokážeme, že třída P je uzavřená na doplněk. Pokud pro libovolný jazyk
K ∈ P existuje deterministický Turingův stroj, který ho rozhoduje s polynomiální časovou
složitostí, záměnou akceptujícího a zamítajícího stavu získáme deterministický
Turingův stroj, který rozhoduje jazyk co−K. Skutečně, pokud původní stroj slovo
akceptoval, nový stroj ho zamítá (a naopak). Navíc záměnou akceptujícího a zamítajícího
stavu se nezmění počet kroků výpočtu, tudíž nový stroj má také polynomiální
časovou složitost. A tedy co−K ∈ P pro libovolné K ∈ P.
Nechť L ∈ P je libovolný jazyk. Ukážeme, že pak platí L ∈ NP ∩ coNP.
Z předchozího tvrzení vyplývá, že také jazyk co−L ∈ P. Protože každý jazyk z P
náleží také do NP (třída P je podtřídou třídy NP – na každý deterministický Turingův
stroj lze nahlížet jako na speciální případ nedeterministického Turingova stroje), víme
také, že L ∈ NP a co−L ∈ NP. Protože co−L ∈ NP, z definice třídy coNP vyplývá
L ∈ coNP. Celkově tedy platí L ∈ NP ∩ coNP pro libovolný jazyk L ∈ P, což jsme
měli dokázat.
(b) Pokud je R regulární jazyk, existuje nějaký totální deterministický konečný automat
A, který ho rozpoznává. Na základě tohoto automatu můžeme sestrojit Turingův
stroj, který bude mít stejné stavy jako automat A a navíc přidaný nový akceptující a
zamítající stav. Tento Turingův stroj bude vstupní slovo postupně číst zleva doprava a
bude simulovat chování automatu A (tj. přepínat se do odpovídajících stavů). Pokud
po dočtení slova stroj skončí ve stavu, který byl v původním automatu akceptující,
přepne se do nového akceptujícího stavu. Jinak se přepne do zamítajícího stavu.
Navíc tento Turingův stroj pro každé vstupní slovo w udělá |w| + 2 kroků: |w| kroků
při čtení slova, jeden při přechodu z levé koncové značky na první písmeno vstupního
slova a jeden při přepínání do akceptujícího/zamítajícího stavu – a proto platí R ∈
TIME(n).
1
IB102 – úkol 11, příklad 2 – řešení Odevzdání: 16. 12. 2013
Vypracoval(a): UČO:
Skupina:
Tuto intuici nyní zachytíme formálně. Buď tedy Σ libovolná abeceda a R ⊆ Σ∗
libovolný regulární jazyk nad touto abecedou. Protože jazyk R je regulární, existuje
totální deterministický konečný automat A = (Q, Σ, δ, q0, F), který ho akceptuje. Na
základě tohoto automatu zkonstruujeme nový Turingův stroj
M = (Q ∪ {qaccept, qreject}, Σ, Σ ∪ { , }, δ , q0, qaccept, qreject).
Kde přechodová funkce
δ : Q × (Σ ∪ { , }) → (Q ∪ {qaccept, qreject}) × (Σ ∪ { , }) × {L, R}
je určená předpisem
δ (q, a) = (δ(q, a), a, R) pro každé q ∈ Q a každé a ∈ Σ,
δ (q, ) = (q0, , R) pro každé q ∈ Q,
δ (q, ) = (qaccept, , R) pro každé q ∈ F,
δ (q, ) = (qreject, , R) pro každé q ∈ Q \ F.
Je zřejmé, že Turingův stroj je deterministický a M akceptuje slovo w, právě když ho
akceptoval automat A. Nyní zjistíme časovou složitost tohoto Turingova stroje. Nechť
tedy w = w1w2 . . . wn je libovolné slovo délky n, kde wi ∈ Σ pro každé 1 ≤ i ≤ n.
Pro každé 1 ≤ i ≤ n označme qi stav, ve kterém se nachází automat A po přečtení i
znaků ze slova w – tedy qi = δ(q0, w1w2 . . . wi).
Turingův stroj M je zkonstruován tak, že přechodová funkce stroje M respektuje
přechodovou funkci automatu A, v každém kroku se čtecí hlava posune doprava a
nikdy se nemění obsah pásky. Proto výpočet Turingova stroje M na slově w je
(q0, w ω
, 0) M (q0, w ω
, 1) M (q1, w ω
, 2) M
M (q2, w ω
, 3) M · · · M (qn, w ω
, n + 1) M (qend, w ω
, n + 2),
kde qend je buď qaccept, nebo qreject (podle toho, jestli automat A slovo w akceptuje,
nebo neakceptuje).
Tedy časová složitost stroje M je funkce TM : N0 → N definovaná pro každé n ∈ N0
vztahem
TM(n) = n + 2.
Tudíž jazyk R je rozhodovaný nějakým Turingovým strojem se složitostí TM(n) ∈
O(n), a proto R ∈ TIME(n).
2