|国家预印本平台
首页|Computable one-way functions on the reals

Computable one-way functions on the reals

Computable one-way functions on the reals

来源:Arxiv_logoArxiv
英文摘要

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.

Xiaoyan Zhang、George Barmpalias

计算技术、计算机技术

Xiaoyan Zhang,George Barmpalias.Computable one-way functions on the reals[EB/OL].(2025-07-17)[2025-08-10].https://arxiv.org/abs/2406.15817.点此复制

评论