8.6 Řekneme, že neorientovaný graf G má k-kliku, pokud v něm existuje úplný podgraf s k vrcholy. Ukažte, že problém
3KLIKA = {<G> | g je graf s 3-klikou}
for(xř y, z) in (V x V x V): if is_clique(x,y,z): accept reject
is_clique(x,y,z): (x,y) \in E a (y,z) \in E a (x,z) \in E
miro
8.3 Rozhodněte, zda je třída NP uzavřená na iteraci. Odpověď zdůvodněte. Následně totéž pro- 8.4 Rozhodněte,
veďte pro třídu P.
(a) LuL2i
(b) L\ £ NI
a
L - j c t v L
"Uhádni" (nedeterministicky vyber) rozdelenie w = w_1, w_2, w_3... w_n
Over že každé wj \in L Akceptuj
Zamietni
Ĺ
Ĺ
míro
ORACLE(Set) =>x\in Set
isjteration(w):
if w is empty v w\in L:
accept split = ORACLE(1..|w|) if w[:split] \in L:
is_iteration(w[split+1:]) else:
reject
miro
isjteration(w):
• w is empty   accept ^
• w\inl_=> accept (Ufo
• for i in 1I w-1 I: ^
• isJteration(w[:i]) a is_iteration(w[i+1:]) -r^ i
• else reject
( /i
j3 ^
6 X
o
■4
- M
4
miro
for i in 1.. I w I:  // slovo dĺžky 1 sa nedá rozdeliť, teda stačí otestovať L
T[i, 1] = w[i] \in L for I in 2.. |w|: for i in 1..(|w| -1 + 1): isjteration = w[i:i+l] \in L forsplit in 1..(l-1):
isjteration = isjteration v (T[i, split] a T[i+split, l-split]) T[i, I] = isjteration returnT[1, |w|] mi
8.4 Rozhodněte, které z následujících tvrzení platí. Odpovědi zdůvodněte.
(a) Li, L2 6 coNP =ř- L1nL2e coNP
(b) Li e NP, L2 C Li, L2 e coNP =► Lx \ L2 € NP
/ 3... w n
6. ^
^ Z. eNÍ   L, c /    /   £ c4 A/P
\
I     " ~
a is_iteration(w[i+1:])
míro