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. 
Wszystkie treści w tym wiki, którym nie przyporządkowano licencji, podlegają licencji:MIT License
Dyskusja
według mnie to jest zupełnie źle - po pierwsze ten wniosek, że zawsze istnieje wielomianowa funkcja obliczająca odwrotność stoi w sprzeczności z zadaniem 120, mówiącym o funkcji jednostronnej - my nie wiemy czy takie funkcje istnieją, ale nie możemy wykluczyć ich istnienia, a wniosek z tego zadania od razu dałby nam odpowiedź, że funkcje jednostronne nie istnieją
poza tym można sobie łatwo wyobrazić funkcję, dla której niektóre argumenty są wykładniczo większe od wartości, więc w twoim rozwiązaniu funkcja nie byłaby w stanie w wielomianowym czasie nawet wypisać wyniku, który byłby wykładniczo większy od argumentu
Masz rację.