按年被提到
20132020 · 2 次2026
算法与数据结构›经典算法与数据结构·arXiv:1301.1547 · cs.CC

Short lists with short programs in short time

Bruno Bauwens, Anton Makhlin, Nikolay Vereshchagin, Marius Zimand · 2013
开始阅读 ↗PDFalphaXiv 讨论
被提及 · 2 人首次 2020-09-21 · 最近 2020-11-16
2不同的人
2活跃月份
2讨论串
6被引(OpenAlex)
arXiv 摘要(候选层不写导读)

Given a machine $U$, a $c$-short program for $x$ is a string $p$ such that $U(p)=x$ and the length of $p$ is bounded by $c$ + (the length of a shortest program for $x$). We show that for any standard Turing machine, it is possible to compute in polynomial time on input $x$ a list of polynomial size guaranteed to contain a O$(\log |x|)$-short program for $x$. We also show that there exists a computable function that maps every $x$ to a list of size $|x|^2$ containing a O$(1)$-short program for $x$. This is essentially optimal because we prove that for each such function there is a $c$ and infinitely many $x$ for which the list has size at least $c|x|^2$. Finally we show that for some standard machines, computable functions generating lists with $0$-short programs, must have infinitely often list sizes proportional to $2^{|x|}$.

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

HN 书评

没有评论直接链到它;下面是它被提交的讨论串里回复最多的评论(不计入统计)

讨论串里没有 ≥100 字的评论,只有提交记录。

被提交为 story · 2 次