We shall show that each nondeterministic single-tape Turing machine of time complexity T(n)
n
2 can be replaced by an equivalent k times faster nondeterministic machine writing only zeroes and ones on its tape, for each k
1. Therefore, nondeterministic single-tape Turing machines do not require the tape compression for speeding-up.