Speeding-up Single-Tape Nondeterministic COmputations by Single Alternation, with Separation Results

摘要

It is shown that for any well behaved function T(n), any single-tape nondeterministic Turing Machine fo time complexity T(n) can be simulated by a single-tape sigma 2-machine in time T(n)/log T(n). A similar result holds also for complementary, single-tape co-nondeter-ministic and II2 machines. Consequently, NTIME sub 1(T(n)) is strictly contained in sigma 2-TIME sub 1(T(n)), and analogously co-TIME sub 1(T(n)) in II sub 2-TIME sub 1(T(n)), i.e., for single tape nondeterministic or co-nondeterministic machines adding of one more alternation leads to provably more powerful machines.