JFiZO - Zadanie 09.113

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.

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.