Computable one-way functions on the reals

June 22, 2024 · The Ethereal · 🏛 Information and Computation

🔮 THE ETHEREAL: The Ethereal
Pure theory — exists on a plane beyond code

"No code URL or promise found in abstract"

Evidence collected by the PWNC Scanner

Authors George Barmpalias, Xiaoyan Zhang arXiv ID 2406.15817 Category cs.CC: Computational Complexity Cross-listed cs.IT, math.LO Citations 2 Venue Information and Computation Last Checked 2 months ago
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. 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.
Community shame:
Not yet rated
📄 View on arXiv 🌐 View on ar5iv 📑 PDF 🎉 Report Code Found
Community Contributions

Found the code? Know the venue? Think something is wrong? Let us know!

📜 Similar Papers

In the same crypt — Computational Complexity