JFiZO - Lista 14
JFiZO - Zadanie 09.109
3COL \le_p NEAR3COL
Graf ma mieć taką własność, że dla każdego wierzchołka może on sąsiadować z conajwyzej jednym wierzchołkiem o takim samym kolorze.
Wówczas można pokazać redukcję 3COL do naszego zmodyfikowanego problemu. Wygląda ona następująco: do każdego wierzchołka v w grafie oryginalnym dodajemy klikę pięcioelementową, łącząc każdy wierzchołek kliki z v (Czyli de facto zastępując pojedyncze wierzchołki sześcioelementowymi klikami).
- \Rightarrow Nowododanych sasiadow v (ktory ma kolor c_1) kolorujemy na: \{c_1, c_2, c_2, c_3, c_3\}.
- \Leftarrow Wierzcholek v o kolorze c_1 nie moze sasiadowac z wierzcholkiem ze starego grafu w o kolorze c_1, poniewaz nie mamy jak przypisac pieciu kolorow wierzcholkom z kliki.
JFiZO - Zadanie 09.113
Dobre rozwiązanie
f(x) = \cases{ n & \mathrm{jeśli} \; 2|n \wedge 2^n = x \cr 2\cdot(x-\left|\{k: 2|k \wedge 2^k < x\}\right|)+1 & \mathrm{w} \; \mathrm{p.p.} }
f jest obliczalna w wielomianowym czasie, natomiast f^{-1} nie jest.
Złe rozwiązanie
f: \{0,1\}^* \rightarrow \{0,1\}^* - obliczalna w wielomianowym czasie. Czy f^{-1} obliczalna w wielomianowym czasie.
Ponumerujmy ciagi zerojedynkowe.
Niech n = f(m). Wtedy f^{-1}(n) obliczymy w nastepujacy sposob:
for (i = 0; ;i++) {
if (f(i) == n)
return i;
}
Funkcja ta oblicza sie w czasie m*zlozonosc_f. 
