Accepting-Path Counting at the One-Tape $n\log n$ Threshold

Ondřej Kuželka

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 m…