A speed-up theorem without tape compression (Q688718)

One of the oldest and best known results on the complexity of Turing machine computations is the constant-factor speed-up result. This theorem states that both the number of steps taken by a Turing machine computation and the number of tape squares visited during this computation may be reduced by an arbitrary constant factor by replacing the original tape alphabet by a compressed form (in general a high- dimensional Cartesian power of this alphabet). In this sense the result represents a trade-off rather than an absolute improvement. The author's result is exceptional in the sense that no trade-off is involved: speed-up without tape compression. The price to be payed is that the result, contrary to the classical result, only holds for a specific model: the single-tape nondeterministic Turing machine. Also the result only holds for weakly time-bounded computations: a strong countability conditions will enable an extension to strongly bounded computations grace to the use of the counter structure invented by M. Fürer. Finally, the result only holds for time bounds above \(O(n^ 2)\); below this bound a similar result can be obtained with a minimal amount of tape compression (one more tape symbol than the machine simulated). The proof technique used is based on a clever selection of partial crossing sequences followed by a local verification of some guessed computation trace; it originates from earlier simulations for single tape machines with the purpose of reducing the amount of tape used. It has been shown that a machine which runs in time \(T(n)\) can be simulated in space \(O(\sqrt{(T(n)})\). Later, it was discovered that for the nondeterministic model this reduction in space consumption can be obtained without loss of time (references 4-7 in the paper). The latter result is an essential ingredient in the proof. A similar technique with a different choice of the size of the tape blocks use used subsequently for obtaining the speed-up in time. So the proof in fact involves two consecutive applications of a crossing sequence argument.