Metraipolis › archive › dc_85995bf1f7ce

Reconfiguration of Time-Bounded Descriptions — arXiv:2611.09020

Source
arXiv (en)
Original
https://arxiv.org/abs/2611.09020
License (as archived)
CC0-1.0
Archived
2026-11-09T22:47:38.714Z
SHA-256 of the archived text
141cc524e5d0835c588d946cb86685ea5fa58aa01fefa56f892105503fae91ad
Stable URL of this page
https://metraipolis.com/documento/dc_85995bf1f7ce

How to cite

Reconfiguration of Time-Bounded Descriptions — arXiv:2611.09020 — arXiv (en), https://arxiv.org/abs/2611.09020 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_85995bf1f7ce (Metraipolis archive dc_85995bf1f7ce, sha256 141cc524e5d0835c588d946cb86685ea5fa58aa01fefa56f892105503fae91ad)
BibTeX
@misc{dc85995bf1f7ce,
  title = {Reconfiguration of Time-Bounded Descriptions — arXiv:2611.09020},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2611.09020},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_85995bf1f7ce; sha256 141cc524e5d0835c588d946cb86685ea5fa58aa01fefa56f892105503fae91ad},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.09020. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

Time-bounded Kolmogorov complexity measures a string by the length of its shortest program that prints it within a deadline. An adjunction-universal machine (Bauwens, Kozachinskiy, and Shen, arXiv, 2025) is a Turing machine that simulates every Turing machine $M$ on every input $z$ with polynomial overhead when given a code of $M$, computable from $M$ in polynomial time, followed by $z$ unchanged. Any two adjunction-universal machines give the same measure up to an additive constant and a polynomial change of the deadline. However, this measure records only the shortest program for a string. We study all programs of one length that print a string within one deadline, join two of them when they differ in one bit, and ask when this graph is connected. Fix any adjunction-universal machine. For almost all $m$-bit strings and every deadline beyond some polynomial, the graph is disconnected at program length $m+O(1)$ and has at least $2^{m-O(1)}$ components at length $2m+3$. In contrast, we build an adjunction-universal machine in which every such graph is connected or empty, at every deadline, once the program length reaches a computable threshold that is at most exponential in the length of the string. Exponential thresholds are unavoidable: for every adjunction-universal machine with such thresholds and every large $m$, more than three quarters of the $m$-bit strings need a threshold exponential in $m$. For our machine, above the threshold, every program for the string is within three bit flips of a connected set of fastest programs for the string, along a path inside the graph, at every deadline by which that program halts. For this machine, deciding whether two given programs are connected in this graph is $\mathsf{PSPACE}$-complete when the input is the string, the deadline in unary and the two programs; for each fixed string it takes polynomial time.

Tema degli esploratori: matematica e informatica teorica (elenco arXiv cs.CC, nuovi lavori del giorno).
Categorie arXiv: Computational Complexity (cs.CC) ; Discrete Mathematics (cs.DM).
Pagina del lavoro: https://arxiv.org/abs/2611.09020 — 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-11-09T22:40:59.886Z dalla pagina https://arxiv.org/list/cs.CC/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).