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 Wj 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á.)
Řešení: Funkce / je vyčíslitelná, počítá ji například následující program.
begin
n := 0; flag := 0;
while flag = 0 do begin y := 7Ti(n); z := 7T2(n);
if Sc{x\, y, z) = 1 A Slc(x2, y, z) = 1 then if        y) = $(x2, y) then /ky := 1;
n := n + 1;
end
Xl :=*(a;i,107); end
Program pro vstup (z, j) postupně prohledává všechny dvojice (y, z) G N2. Pro každou dvojici ověří, zda programy Pí a Pj skončí na vstupu y během z kroků (a tudíž y e Wi d Wj) a následně zda ifi(y) = <fij(y)- Pokud dvojice splní obě podmínky, program vrátí hodnotu y>j(107).
2. (4-0 bodů) Binární operaci o na množinách i,BCN definujeme jako AoB = {í\íeAa,íje sudé} U {í | í G B a í 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.
Řešení: Obě třídy jsou uzavřené na operaci o.
(a) Nechť A, B C N jsou rekurzivní množiny. Pak jejich charakteristické funkce XAi Xb Jsou TVF. Množina AoB je také rekurzivní, neboť její charakteristická funkce je vyčíslitelná například tímto programem:
begin
y := x\ mod 2; if y = 0 then xx := xa(xi); if y = 1 then xx := xb(xi); end
(b) Nechť A, B jsou r.e. množiny, tedy A = dom{(pi) a B = dom(ífj) pro nějaké i, j G N. Množina AoB je také r.e., protože je definičním oborem vyčíslitelné funkce počítané tímto programem:
begin
y := x\ mod 2; if y = 0 then <í>(z,aľi); if y = 1 then <í>(j, xi); end
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}.
Řešení: Nejprve ukážeme, že DOUBLE-CLIQUE G N P. Problém rozhoduje například nedeterministický TM, který nejdříve zjistí, zda vstup je tvaru (G, k). Pokud tomu tak není, stroj zamítne. Je-li k větší než počet vrcholů v grafu G, stroj také zamítne. Nyní stroj nedeterministicky vybere dvě podmnožiny vrcholů grafu G tak, aby každá obsahovala právě k vrcholů. Pokud jsou tyto množiny totožné nebo mají prázdný průnik, stroj zamítne. Nyní stačí ověřit, že vrcholy v každé množině tvoří fc-kliku. Pokud tomu tak je, stroj akceptuje. V opačném případě zamítne. Popsaný výpočet lze provést v polynomiálním počtu kroků vzhledem k velikosti vstupu.
NP-těžkost dokážeme redukcí CLIQUE <p DOUBLE-CLIQUE z NP-úplného problému CLIQUE. Redukční funkci / definujeme takto:
• Pokud vstupní řetězec není kódem dvojice (G,k), pak funkce / dá na výstup stejný řetězec.
• Je-li vstupem kód dvojice (G, k), pak funkce / vrátí kód (G', k + 1), kde G' je graf obsahující dvě kopie grafu G a navíc jeden přidaný vrchol, který má hranu do každého vrcholu. Pokud G = (V, E), pak G' formálně definujeme jako (V', E'), kde V' = {v, v' \ v G V} U {w} a E' = {{v1,v2},{v'1,v'2} | {v!,v2} G E}u{{v,w},{v',w} | v G V}. Pokud graf G obsahoval n vrcholů, pak G' obsahuje 2n + 1 vrcholů.
Redukční funkce je zjevně totálně vyčíslitelná deterministickým TM pracujícím v polynomiálním čase.
Zbývá dokázat, že x e CLIQUE ^=> f(x) G DOUBLE-CLIQUE.
=^>" Pokud x G CLIQUE, pak x je kódem dvojice (G, k), kde G obsahuje fc-kliku. Nechť W je množina vrcholů této fc-kliky. Pak G' obsahuje dvě (k + l)-kliky, kde jedna je tvořena vrcholy W U {w} a druhá vrcholy {v' \ v G W} U {w}. Jedná se o různé kliky, které však mají společný vrchol w. Tedy f(x) = (G', k + 1) G DOUBLE-CLIQUE.
Pokud f(x) G DOUBLE-CLIQUE, pak f(x) = (G',k + 1) a G' je graf obsahující dvojitou (fc+l)-kliku. Vezměme jednu z těchto (fc + l)-klik. Jelikož graf G' neobsahuje žádnou hranu spojijící dvě kopie grafu G, tak celá tato (k + l)-klika musí leže v jedné kopii grafu G rozšířené o vrchol w. Vypustíme-li z této (k + l)-kliky
— vrchol w, pokud je v ní obsažen, nebo
— jeden libovolný vrchol, pokud (k + l)-klika neobsahuje w,
získáme nutně fc-kliku v jedné z kopií grafu G. Graf G tedy obsahuje k-kliku a proto platí x G CLIQUE.