one-way function

Abstract We study the complexity of deterministic and probabilistic inversions of partial computable functions on the reals. Content Overview We regard a Turing functional $f$ as a (possibly partial) map (function) from $2^\omega$ to $2^\omega$, that is, $f(x)$ is the real $y$ such that $y(n)=f^x(n)$ (the output of $f$ with oracle $x$ and input $n$) for all $n$.

Abstract A major open problem in computational complexity is the existence of a one-way function, namely a function from strings to strings which is computationally easy to compute but hard to invert.