One-tape turing machines show sharp change in counting complexity
Accepting-Path Counting at the One-Tape $n\log n$ Threshold
Computational Complexity
Summary
Some computer models called one-tape Turing machines run tasks and count their possible solutions. The authors found that if such a machine runs faster than roughly n times log n steps, the counting pattern of solutions is simple and predictable. But if it runs at n times log n steps or slower, the counting becomes very complex, even matching the difficulty of some well-known hard problems. They also showed examples where the number of solutions grows in a way that can't be calculated by any algorithm.
What this means in practice
- •For complexity theorists: Use the sharp time threshold in one-tape machines to classify counting problems by their computational difficulty.
- •For algorithm designers: Understand which counting tasks are tractable or inherently complex when designing algorithms constrained by one-tape machines.
A theory result. No direct application yet.
Authors
Ondřej Kuželka
Abstract
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.