按年被提到
20002021 · 1 次2026
数学、逻辑与理论›范畴论与逻辑·arXiv:cs/0012023 · cs.CR

The Tale of One-way Functions

Leonid A. Levin · 2000
开始阅读 ↗PDFalphaXiv 讨论
被提及 · 2 人首次 2021-03-17 · 最近 2022-04-06
2不同的人
2活跃月份
2讨论串
6被引(OpenAlex)
arXiv 摘要(候选层不写导读)

The existence of one-way functions is arguably the most important problem in computer theory. The article discusses and refines a number of concepts relevant to this problem. For instance, it gives the first combinatorial complete owf, i.e., a function which is one-way if any function is. There are surprisingly many subtleties in basic definitions. Some of these subtleties are discussed or hinted at in the literature and some are overlooked. Here, a unified approach is attempted.

候选层:至少 2 个不同的人、在 2 个不同月份提到过,还没到主书架的 3 人 3 个月。没有做立场标注,所以只写“被提及”。

HN 书评

推荐在前,同类按时间 · 每篇最多保留 20 条,统计用全部提及
评论gnull · 2022-04

“Identifying the connection between one-way functions and Kolmogorov complexity is truly impressive. But the article oversimplified a few things that may be misleading for someone. 1. One-way functions are not all cryptography. Some constructions may need stronger assumptions than one-way functions (we don't know yet if they do). So this problem is a “Mas…”

The existence of true one-way functions depends on Kolmogorov complexity原评论 ↗
被提交为 story · 1 次