Složitost – cvičení
13.1 Rozhodněte, které z následujících vztahů platí. Odpovědi zdůvodněte.
a) 2 ∈ ( )
b) ∈ ( )
c) log ∈ ( )
d) log ∈ ( )	
e) 3 ∈ 2 ( )
f) 3 + 4 + 17 ∈ ( − + 1)
g) (2 )! ∈ ( ! )
Řešení:
a) Platí. Zvolme = 1 ∧ = 2. Pak určitě platí, že 2 = ( ) ≤ ⋅ ( ) = 2 pro všechna
≥ 1.
b) Neplatí. Sporem předpokládejme, že existují konstanty , takové, že ≤ ⋅ pro ≥
. Nerovnici podělíme nenulovým kladným číslem n: ≤ . Ať volíme konstanty , , jak
chceme, vždy budou existovat množina přirozených čísel = ! ", " + 1, … $,	kde " = ⌈ ⌉,
taková, že pro všechna ' ∈ neplatí vztah ' ≤ .
c) Platí. Zvolme = 1 ∧ = 1. Pak určitě platí, že log = ( ) ≤ ⋅ ( ) = pro
všechna ≥ 1.
d) Neplatí. Sporem předpokládejme, že existují konstanty , takové, že log ≤ ⋅ pro
≥ . Nerovnici podělíme nenulovým kladným číslem n: log ≤ . Ať volíme konstanty
, , jak chceme, vždy budou existovat množina přirozených čísel = ! ", " + 1, … $,	kde 	
" = 2()*
, taková, že pro všechna ' ∈ neplatí vztah log ' ≤ .
e) Platí. Z definice platí, že ( ) ∈ 2 ( )
⇔ ∃ , ∈ -: ( ) ≤ 2(⋅
	pro všechna ≥ . My
hledáme tyto konstanty tak, aby 	
(∗)	3 ≤ 2(⋅
= (2 )(
.
Zvolme = 2, = 1. Pak (2 )(
= (2 ) = 2 = 4 . Jistě tedy pro libovolné ≥ 1 platí
3 ≤ 2(⋅
= 4
f) Platí. Zvolme = 4. K optimální volbě dospějeme řešením nerovnice
3 + 4 + 17 ≤ 4 ⋅ ( − + 1)	
(∗)	0 ≤ − 5 − 16	
Buď spočítáním diskriminantu nebo odhadem usoudíme, že pro ≥ 8 vztah (∗) platí.
Hledanou konstantou je = 8.
g) Neplatí. Sporem předpokládejme, že
(∗)	existují konstanty , takové, že (2 )! ≤ ⋅ ( !) pro všechna ≥ .
Zvolme 4 = max!1, , $ a dosaďme do vztahu (∗):
(24)! ≤ ⋅ (4!)
24 ⋅ (24 − 1) ⋅ … ⋅ (4 + 1) ⋅ 4! ≤ ⋅ 4! ⋅ 4! (podělíme nerovnici kladným výrazem 4!)
(∗∗)	24 ⋅ (24 − 1) ⋅ … ⋅ (4 + 1) ≤ ⋅ 4 ⋅ (4 − 1) ⋅ … ⋅ 2 ⋅ 1
Protože ≤ 4, vztah (∗∗) nemůže nikdy platit. Spor s předpokladem (∗).
13.3 Dokažte, že třída P je uzavřená na operace sjednocení, komplement a zřetězení. Rozhodněte, na
které z těchto operací je uzavřena třída NP. Odpověď zdůvodněte.
Řešení:
Nejprve připomeňme: P je třída všech jazyků L, pro které existuje deterministický TM s polynomiální
časovou složitostí, který rozhoduje L. Zejména tedy platí, že každý jazyk 8 ∈ 9 je rekurzivní. Z toho
však vyplývá, že třída P je uzavřena na všechny tři operace.
Třída NP obsahuje všechny jazyky L, pro které existuje nedeterministický TM s polynomiální časovou
složitostí, který rozhoduje L. V případě operací sjednocení a zřetězení použijeme postup, který byl
aplikován v kapitole o uzávěrových vlastnostech tříd rekurzivních a rekurzivně spočetných jazyků.
Buďte :, ; nedeterministické TM, které rozhodují jazyky <, = v čase ( "
),	resp. ( >
), kde ?, @
jsou vhodná přirozená čísla.
Nedeterministický Turingův stroj A pro jazyk < ∪ = sestrojíme tak, že se na začátku
nedeterministicky rozhodne, zda bude simulovat práci TM : či ;. V případě, že simulace skončí
v akceptujícím stavu, tak A akceptuje. V opačném případě zamítá. Stroj A na začátku učiní jeden
krok (výběr stroje k simulace), následně v čase ( "
) či ( >
) simuluje výpočet vybraného stroje, a
poté na závěr učiní poslední krok, v němž se přepne buď do akceptujícího nebo do zamítajícího stavu.
V každém případě bude opět pracovat v polynomiálním čase.
Nedeterministický Turingův stroj C pro jazyk <. = sestrojíme tak, že se na začátku nedeterministicky
rozdělí vstup D na dvě části D*. D . Následně spustí simulaci TM : na slově D*	v čase ( "
).
Akceptuje-li : slovo D*, spustí C výpočet ; na slově D . V případě, že simulace skončí
v akceptujícím stavu, tak C akceptuje, v každém jiném případě, kdy : zamítá D* nebo ; zamítá
slovo D , zamítá i stroj C. Stroj C na začátku učiní jeden krok (nedeterministické rozdělení slova
D), následně v čase ( "
) + ( >
) simuluje výpočet obou strojů na slovech D*, D . V každém
případě bude opět pracovat v polynomiálním čase.
O uzavřenosti třídy NP na doplněk nelze rozhodnout. Řešením by mohla být záměna akceptujícího a
zamítajícího stavu, která fungovala v případě důkazu uzavřenosti třídy rekurzivních jazyků na
doplněk. Výpočtů na nějakém slově D však může být v případě nedeterministického TM M mnoho.
Platí:
1. D ∈ 8( ) ⇔ existuje akceptující výpočet M na w;
2. w nepatří do 8( ) ⇔ všechny možné výpočty M na w skončí v zamítajícím stavu.
Výměnou akceptujícího a zamítajícího stavu nedokážeme vyřešit ty situace, kdy pro dané slovo D
bude řada zamítajících i akceptujících výpočtů.
13.4 Třída coNP je definována jako coNP = !co − 8 ∣ 8 ∈ NP$. Rozhodněte, které z následujících
tvrzení platí. Odpovědi zdůvodněte.
a) coNP = co − NP
b) 8*, 8 ∈ coNP ⇒ 8* ∩ 8 ∈ coNP
c) 8* ∈ NP, 8 ⊂ 8*, 8 ∈ coNP ⇒ 8* ∖ 8 ∈ NP
Řešení:
a) Neplatí. Protipříkladem může být jakýkoliv jazyk 8 ∈ P. Díky uzavřenosti třídy P na operaci
doplněk platí též co − 8 ∈ P ⊆ NP. Jazyk co − 8 ∈ coNP, avšak co − 8 nepatří do co − NP.
b) Platí. Protože 8*, 8 ∈ coNP, znamená to dle definice, že co − 8*, co − 8 ∈ NP. V příkladu
13.3 jsme ukázali, že třída NP je uzavřena na sjednocení. Platí tedy 	
co − 8* ∪ co − 8 = co − (8* ∩ 8 ) ∈ NP.
Proto 8* ∩ 8 ∈ coNP.
c) Platí. Protože 8 ∈ coNP, je dle definice co − 8 ∈ NP. Platí také vztah
8* ∖ 8 = 8* ∩ co − 8 .	
Navíc, třída NP je uzavřena na průnik (důkaz podobný jako v případě uzavřenosti rekurzivních
a rekurzivně spočetných jazyků na průnik). Protože 8*, co − 8 ∈ NP, je i 	
8* ∩ co − 8 = 8* ∖ 8 ∈ NP.
13.6 Dokažte, že následující problémy jsou NP-úplné.
a) Problém Hamiltonovské cesty v grafu:
HAMPATH = !〈O, P, Q〉 ∣ O je orientovaný graf obsahující Hamiltonovskou cestu z s do t$
b) Problém k-kliky (k-klika je úplný podgraf s k vrcholy):
CLIQUE = !〈O, ?〉 ∣ O je neorientovaný graf s k-klikou$
c) Problém podgrafového izomorfismu (Subgraph Isomorphism, SGI):
SGI = !〈S, O〉 ∣ S = (T, U), O = (V, W) jsou neorientované grafy takové, že existuje injektivní
zobrazení : T → V splňující (Y, YZ) ∈ U ⇒ [ (Y), (YZ)\ ∈ W$
Řešení:
a) HAMPATH – řešení viz Sipser, kap. 7, důkaz Theoremu 7.35 začínající na str. 262
b) CLIQUE
Důkaz CLIQUE ∈ NP: Setrojíme nedeterministický TM M pracující pro vstup 〈O, ?〉 takto:
1. Nejprve zjistí, zda vstup je tvaru 〈O, ?〉, kde O je neorientovaný graf a k je přirozené číslo.
Pokud ne, M zamítne.
2. Nechť O = (T, U), kde V je množina vrcholů, E množina hran. Nedeterministicky zvol
množinu vrcholů V ⊆ T, |V| = ?.
3. Ověř, zda U je úplný podgraf grafu G.
a. Pokud ano, akceptuj.
b. V opačném případě zamítni.
Části 1, 2 lze provést polynomiálním počtu kroků. Je-li = |〈O, ?〉| délka vstupu TM M, pak ověření
korektnosti vstupu zabere ( ) času. Nedeterministická volba k vrcholů také nezabere víc než ( )
kroků. Ověření, zda k vrcholů je spojeno hranami, každý s každým, znamená ověřit (? − 1) ⋅ … ⋅ 2 ⋅ 1
hran. Jde o konstantní počet kroků nezávisející na délce vstupu. Všechny části, kterých je
polynomiálně mnoho, lze tedy provést v polynomiálním čase.
Důkaz 3SAT ≤g CLIQUE: Buď Φ = (i* ∨ k* ∨ *) ∧ (i ∨ k ∨ ) ∧ … ∧ (i" ∨ k" ∨ ") Booleovská
formule ve 3cnf. Redukce f vyprodukuje kód 〈O, ?〉, kde G je neorientovaný graf. Vrcholy budou
uspořádány do k trojic, jejich názvy budou označeny literály příslušných klauzulí. Vrcholy jedné trojice
nebudou spojené hranami. Hrany povedeme napříč trojicemi (klauzulemi) dle tohoto pravidla.
Libovolný vrchol '	Qrojice Ql spojíme hranou s vrcholem m trojice Qn (o ≠ q) pouze tehdy, je-li m ≠ ¬'.
Příklad takového grafu, viz Sipser, kap. 7, obr. 7.7.
Chceme ukázat, že 3cnf formule Φ je splnitelná právě tehdy, když (Φ) = 〈O, ?〉 je neorientovaný
graf, v němž existuje k-klika.
1. Předpokládejme, že Φ = (i* ∨ k* ∨ *) ∧ (i ∨ k ∨ ) ∧ … ∧ (i" ∨ k" ∨ ")	 je splnitelná
3cnf formule. To znamená, že v každé klauzuli je alespoň jeden z literálů pravdivý. Např. jde o
množinu s = !i*, k , t, … , k"$.	V orientovaném grafu G jistě musí být hrana mezi každou
dvojicí vybranou z S. Pokud by např. pro dvojici !i*, k $ nebyla, znamenalo by to případ, že
k = ¬i*. To ovšem není možné, nemůže být pravdivý literál i* i jeho negace ¬i*. Množina
vrcholů S tedy tvoří k-kliku v grafu G.
2. Předpokládejme, že graf G disponuje k-klikou. Dle pravidel konstrukce žádné dva vrcholy kliky
nejsou ve stejné trojici. Ohodnocení proměnných provedeme tak, že každý vrchol kliky (tj.
literál, ať už v pozitivní či negativní formě) bude pravdivý. Protože hranou nejsou spojeny dva
vrcholy s návěštím ', ¬', dosáhneme ohodnocení, které pro každou klauzuli bude znamenat
alespoň jeden pravdivý literál, tj. celá formule Φ sestavená z jednotlivých trojic grafu G
tvořících klauzule bude splnitelná.
c) SGI
Důkaz SGI ∈ NP: Setrojíme nedeterministický TM M pracující pro vstup 〈S, O〉 takto:
1. Nejprve zjistí, zda vstup 〈S, O〉 kóduje dva neorientované grafy S = (T, U) a O = (V, W).
Pokud ne, M zamítne.
2. Nedeterministicky zvolí zobrazení : T → V	takové, aby bylo injektivní.
3. Pro každou hranu !v*, v $ ∈ U	ověří, zda ! (v*), (v )$ ∈ W. Pokud ne, zamítá.
4. Stroj M akceptuje, pokud testy v předchozím bodu byly pro všechny hrany úspěšné.
Všechny čtyři části lze provést v polynomiálním počtu kroků.
Důkaz CLIQUE ≤g SGI: Mějme kód 〈O, ?〉. Sestrojíme funkci , která nejprve ověří, zda
• 〈O, ?〉 skutečně kóduje dvojici neorientovaný graf O = (T, U) a přirozené číslo k;
• |T| ≥ ?
Pokud jedna z podmínek neplatí, nastavíme pro kód x funkci f takto:
(〈'〉) = 〈O*, O 〉,
kde oba grafy budou mít pouze jeden vrchol, přičemž O* bude mít u svého vrcholu smyčku, množina
hran O bude prázdná. Jistě kód 〈O*, O 〉 nepatří do SGI. Platí-li obě podmínky, nastavíme funkci f
takto:
(〈O, ?〉) = 〈O, S"〉,
kde S" je úplný neorientovaný graf s k vrcholy. Jistě platí, že 〈O, ?〉 ∈ CLIQUE ⇔ 〈O, S"〉 ∈ SGI
(ověření obou stran implikace je tentokrát zřejmé). Redukce f je sestrojena tak, že reaguje na všechny
možné vstupy, i když není zadána dvojice (graf, číslo). Ověření obou uvedených podmínek jistě
probíhá v polynomiálním čase. Sestrojení grafů O*, O je také nenáročné na čas. Vytvoření grafu S" je
také možné zvládnout polynomiálně. Následné ověření podmínky 〈O, S"〉 ∈ SGI sice probíhá
nedeterministicky, ale v polynomiálním čase, protože jsme ověřili platnost SGI ∈ NP.
13.7 Určete vztahy inkluze/rovnost mezi následujícími dvojicemi složitostních tříd. Svoje tvrzení
zdůvodněte.
a) TIME( ) a TIME( t
)
b) SPACE(2 ) a SPACE(100 )
c) SPACE( ) a TIME( )
d) NSPACE( ) a SPACE( x
)
e) P a TIME(2 )
Řešení:
a) TIME( ), resp. TIME( t)	jsou třídy jazyků rozhodovaných nějakým deterministickým
jedno- či vícepáskovým TM s časovou složitostí ( ), resp. ( t
). Jistě platí ∈ ( t
).
Proto jazyk 8 ∈ TIME( ) patří i do třídy TIME( t), tedy TIME( ) ⊆ TIME( t
).
b) V obou případech platí, že (? ⋅ ) = ( ). Proto se třídy rovnají, tj. platí
SPACE(2 ) = SPACE(100 ).
c) Z přednášky (poslední přednášková sada, slajd 20) víme, že pro každou funkci : -y → z)
platí TIME[ ( )\ ⊆ SPACE( ( )). Jistě tedy platí vztah TIME( ) ⊆ SPACE( ).
d) Podle Savitchovy věty platí vztah NSPACE( ) ⊆ SPACE( {
). Dále je zřejmé, že {
∈ ( x
),
tj. SPACE( {) ⊆ SPACE( x
). Z obou vztahů tedy vyplývá NSPACE( ) ⊆ SPACE( x
).
e) P je třída jazyků rozhodovaných nějakým deterministickým jedno- či vícepáskovým TM s
polynomiální časovou složitostí ( "
). Zcela jistě "
∈ (2 ) pro každé přirozené k. Tedy
9 ⊆ |} U(2 ).