Metraipolis › archive › dc_8eb67f44d44b
On Computational Hardness of Mistake-Bounded Language Generation: A Random-Oracle Query Separation — arXiv:2608.05029
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2608.05029
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-31T11:59:52.757Z
- SHA-256 of the archived text
42913c28726b296df2b7f00d220c38adf5ec2d037aa021e98d7d897349610b89- Stable URL of this page
https://metraipolis.com/documento/dc_8eb67f44d44b
How to cite
On Computational Hardness of Mistake-Bounded Language Generation: A Random-Oracle Query Separation — arXiv:2608.05029 — arXiv (en), https://arxiv.org/abs/2608.05029 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_8eb67f44d44b (Metraipolis archive dc_8eb67f44d44b, sha256 42913c28726b296df2b7f00d220c38adf5ec2d037aa021e98d7d897349610b89)
BibTeX
@misc{dc8eb67f44d44b,
title = {On Computational Hardness of Mistake-Bounded Language Generation: A Random-Oracle Query Separation — arXiv:2608.05029},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2608.05029},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_8eb67f44d44b; sha256 42913c28726b296df2b7f00d220c38adf5ec2d037aa021e98d7d897349610b89},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.05029. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
Generation in the limit guarantees eventual generation for every countable collection of infinite languages in the model of Kleinberg and Mullainathan [KM24], while closure dimension characterizes stronger information-theoretic guarantees [RLT25]. Neither restricts per-output computation. The cumulative-mistake objective in mistake-bounded generation makes finite failure prefixes quantitative [KPR26], and a per-output query budget exposes their computational source. Polynomial-time algorithms are known for parities, conjunctions, and monotone functions with polynomially many maxterms [JKO26]. We ask whether information-theoretic ease can coexist with bounded-access computational hardness. Relative to a random oracle $H$, we answer yes by constructing a countable collection $C^\star$ of infinite languages with closure dimension zero. Almost surely on the same $H$, an unbounded generator makes zero mistakes on every target and every complete distinct enumeration. Yet, writing $\lambda$ for the target-seed length, every fixed uniform generator $G$ with polynomially many oracle queries in $\lambda$ and the output index $i$ has a constant $c_G>0$ such that, for every sufficiently large $\lambda$, some target incurs more than $2^{c_G\lambda}$ expected mistakes within its first $2(\lceil 2^{c_G\lambda}\rceil+1)$ canonical outputs. Infinite accidental agreement enables exhaustive search; sparse queries hide fresh target values. Thus, in the random-oracle model, zero-mistake information-theoretic generation coexists with a generator-dependent exponential lower bound on worst-case expected mistakes under polynomial-query access.
Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-08-06 in cs.CC).
Categorie arXiv: Computational Complexity (cs.CC).
Pagina del lavoro: https://arxiv.org/abs/2608.05029 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-31T11:48:08.823Z dalla pagina https://arxiv.org/catchup/cs.CC/2026-08-06?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).