Inverting a One-to-One Real Function Is Inherently Sequential
Ker‐I Ko · Birkhäuser Boston eBooks · 1990
It is well known that the root, as well as the inverse function, of a one-to-one, polynomial-time computable real function fon [0,1] can be computed in polynomial time by binary search, if its inverse function has a polynomial modulus. We show that unless P = LOGSPACE the problem of inverting a one-to-one function cannot be done in log space even if the function f itself is log-space computable and its inverse function has a polynomial modulus.