Alternating time versus deterministic time: a separation
S. Gupta · 2002
It is shown that only two alternations are sufficient to achieve a log*t(n) speed-up of deterministic Turing machines. Using this speed-up it is shown that for each time-constructible function t(n), two alternations are strictly more powerful than deterministic time.>