Složitost
13.1 Rozhodněte, které z následujících vztahů platí. Odpovědi zdůvodněte.
a) 2n e O (n)
b) n2 G O (n)
c) nlog2 n G 0(n2)
d) nlog2 n G O (n)
e) 3™ G 2°(")
f) 3n2 + 4n + 17 G 0(n2 - n + 1)
g) (2n)!eO(n!2)
13.2 Rozhodněte, zda platí následující vztah. Odpověď zdůvodněte.
g(n)ČO(f(n)) /(n)eo(ff(n))
13.3 Dokažte, že třída P je uzavřená na operace sjednocení, komplenient a zřetězení. Rozhodněte, na které z těchto operací je uzavřena třída NP. Odpověď zdůvodněte.
13.4 Třída coNP je definována jako coNP = {co—L | Z e NP}. Rozhodněte, které z následujících tvrzení platí. Odpovědi zdůvodněte.
a) coNP = co-NP
b) Li,L2ecoNP =^> LinL2ecoNP
c) Li e NP, Z2 C Za, Z2 G coNP =^> Zi \ Z2 e NP
13.5 Rozhodněte, zda jsou následující formule splnitelné. U splnitelných formulí popište nějaké splňující přiřazení.
a) (x V y) A (x V ^y) A (^x V y) A (^x V ^y)
b) (x V -.y) A (x V y V z) A (-.x V -.y) A (-.x V y) A (x V ^z)
c) (x V -ny) A (x V ^y V z) A (->x V -ny) A (->x V y) A (x V ^z)
d) (iiV^dV -w) A (w V ^y V z) A (w V ^z V x) A (x V y V z)
e) (x V y V z) A (->x V y V z) A (x V ^y V z) A (x V y V ^z) A (->x V ^y V z) A (x V ^y V ^z) A (->x V ^y V ^z)
13.6 Dokažte, že následující problémy jsou NP-úplné.
a) Problém Hamiltonovské cesty v grafu:
HAMPATH = {(G, s,t) \ G je orientovaný graf obsahující Hamiltonovskou cestu z s do ŕ}
b) Problém k-kliky (k-klika je úplný podgraf s k vrcholy): CLIQUE = {(G, k) | G je neorientovaný graf s fc-klikou}
c) Problém podgrafového izomorŕismu (Subgraph Isomorphism, SGI):
SGI = {(ZZ, G) | ZZ = (V,E),G = (U, F) jsou neorientované grafy takové, že existuje injektivní zobrazení / : V —>• U splňující (u, u') G E => (f (u), f (u1)) e F}
23
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(n2) a TIME(n3)
b) SPACE(2n2) a SPACE(100n2)
c) SPACE(n2) a TIME(n2)
d) NSPACE(n2) a SPACE(n5)
e) P a TIME(2")
13.8 Zkonstruujte jednopáskový deterministický Turingův stroj, který rozhoduje jazyk L = {{)klk \ k > 0} v čase C(nlogn). Není nutné uvádět formální popis stroje.
24