IB 107 Vyčíslitelnost a složitost
0. ledna 2021, 100 minut
1. (25 bodu) Rozhodněte, zda je následující funkce / : N2 —>• N vyčíslitelná.
í ^(107) pokud pro nějaké y G n W} platí ^(y) = ipj(y) I  _L jinak
Své rozhodnutí dokažte. (Pro důkaz, že funkce je vyčíslitelná, stačí napsat while-program, který ji počítá.)
2. (4-0 bodů) Binární operaci o na množinách i,BCN definujeme jako
AoB = {i\ieAa,ije sudé} U {i | i G B a i je liché}. Rozhodněte a dokažte, zda je na tuto operaci uzavřená
(a) třída všech rekurzivních množin,
(b) třída všech rekurzivně spočetných množin.
3. (35 bodů) Řekneme, že neorientovaný graf obsahuje dvojitou k-kliku pro dané k > 1, pokud obsahuje dvě různé k-kliky, které sdílí alespoň jeden společný vrchol. Dokažte, že problém rozhodnout, zda daný neorientovaný konečný graf G pro dané k obsahuje dvojitou fc-kliku, je NP-úplný. Formálně problém definujeme jako množinu
DOUBLE-CLIQUE ={(G,k)\G je graf obsahující dvojitou fc-kliku}.