Computable one-way functions on the reals
<|reference_start|>Computable one-way functions on the reals: 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. Levin (2023) formulated the notion of one-way functions from reals (infinite bit-sequences) to reals in terms of computability, and asked whether partial computable one-way functions exist. We give a strong positive answer using the hardness of the halting problem and exhibiting a total computable one-way function.<|reference_end|>
@article{barmpalias2024computable,
    title={Computable one-way functions on the reals},
    author={George Barmpalias and Xiaoyan Zhang},
    journal={arXiv preprint arXiv:2406.15817},
    year={2024},
    archivePrefix={arXiv},
    eprint={2406.15817},
    primaryClass={cs.CC cs.IT math.IT math.LO}
}