computable analysis

Abstract Oneway real functions are effective maps on positive-measure sets of reals that preserve randomness and have no effective probabilistic inversions. We construct a oneway real function which is collision-resistant: the probability of effectively producing distinct reals with the same image is zero, and each real has uncountable inverse image.

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 One-way functions are the functions that are easy to compute but hard to invert. In terms of oracle Turing machines, we can formalize the notion of computable functions from reals to reals, and define it to be one-way if computable functions almost everywhere fails to invert it.

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.