Title :
Alternating time versus deterministic time: a separation
Author_Institution :
Dept. of Comput. & Inf. Sci., Ohio State Univ., Columbus, OH, USA
Abstract :
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
Keywords :
Turing machines; computational complexity; deterministic automata; alternating time; deterministic Turing machines; deterministic time; time-constructible function; Complexity theory; Computational modeling; Legged locomotion; Polynomials; Turing machines;
Conference_Titel :
Structure in Complexity Theory Conference, 1993., Proceedings of the Eighth Annual
Conference_Location :
San Diego, CA
Print_ISBN :
0-8186-4070-7
DOI :
10.1109/SCT.1993.336520
