Cvičná písomka: UČO: Jméno:
1. Rozhodnite a zdôvodnite:
(a) (2b). n ∈ o(n · log(n))
(b) (2b). 4n
∈ O(2n
)
(c) (2b). 2n
∈ 4Ω(n)
2 (4b). Predpokladajte P = NP. Rozhodnite a zdôvodnite, či je daný problém v P alebo je
NP-úplný:
IND#7 = {G | graf G obsahuje nezávislú množinu veľkosti aspoň 7 }
3 (4b). Dokážte že 3SAT ≤p 4SAT a že 4SAT ∈ NP, pričom problém 4SAT definujeme
nasledovne:
4SAT = {Φ | Φ je splniteľná booleavská formula v CNF ktorej klauzule majú presne 4 literály }
(CNF = konjunktívna normálna forma)
4 (6b). Navrhnite numerujúcu funkciu fG všetkých neorientovaných grafov (Neorientovaný graf
chápeme ako dvojciu množín (V, E) pričom prvky E sú dvojprvkové podmnožiny V ).
Pozn.: numerujúca funkcia nemusí byť prostá, musí byť však surjektívna - každý graf môže
mať viacero indexov, musí mať však aspoň jeden.