Metraipolis › archive › dc_a9c8b9531db0
Accepting-Path Counting at the One-Tape $n\log n$ Threshold — arXiv:2609.32959
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.32959
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-08T00:43:19.744Z
- SHA-256 of the archived text
0bd31eb1616407b2a11a25061735c306d000c360ff1c6dac156033af9c9fda87- Stable URL of this page
https://metraipolis.com/documento/dc_a9c8b9531db0
How to cite
Accepting-Path Counting at the One-Tape $n\log n$ Threshold — arXiv:2609.32959 — arXiv (en), https://arxiv.org/abs/2609.32959 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_a9c8b9531db0 (Metraipolis archive dc_a9c8b9531db0, sha256 0bd31eb1616407b2a11a25061735c306d000c360ff1c6dac156033af9c9fda87)
BibTeX
@misc{dca9c8b9531db0,
title = {Accepting-Path Counting at the One-Tape $nlog n$ Threshold — arXiv:2609.32959},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.32959},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_a9c8b9531db0; sha256 0bd31eb1616407b2a11a25061735c306d000c360ff1c6dac156033af9c9fda87},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.32959. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
We observe that the classical $n\log n$ time threshold for one-tape Turing machines is also a threshold for their accepting-path counts. Below it, every nondeterministic one-tape machine running in strong $o(n\log n)$ time has a rational ordinary generating function of accepting-path counts. At strong $O(n\log n)$ time, the situation changes completely: there is a fixed one-tape machine whose accepting-path function is complete for $\#\mathsf P_1$, the tally analogue of $\#\mathsf P$, under parsimonious polynomial-time tally reductions. A second construction within the same time bound gives positive accepting-path counts with a noncomputable exponential growth rate. The rationality result combines the one-tape time gap with the linear-time counting theorem of Tadaki, Yamakami and Lin. The completeness proof adapts the linear-time universal counting machine of Beame et al. to the one-tape setting. Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-29 in cs.CC). Categorie arXiv: Computational Complexity (cs.CC). Pagina del lavoro: https://arxiv.org/abs/2609.32959 — 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-08T00:17:42.544Z dalla pagina https://arxiv.org/catchup/cs.CC/2026-09-29?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).