Nondeterministic and alternating computations
Jie Wang, Luc Longpré · 2003
This paper proves that alternating computations with O(t(n)) time can simulate nondeterministic computations with O(t(n) log* t(n)) time and O(t(n)) nondeterministic moves. From this the authors prove that nondeterministic linear time is not closed under complementation if nondeterministic Turing machines with O(n log* n) time and linear nondeterministic moves are strictly more powerful than nondeterministic linear time.>