On log-time alternating Turing machines of alternation depth k
Conference Paper
Overview
Identity
Additional Document Info
Other
View All
Overview
abstract
Springer-Verlag Berlin Heidelberg 1995. Several input read-modes for alternating Turing machines have been proposed in the literature. For each input read-mode and for each fixed integer k 1, a precise circuit characterization is established for log-time alternating Turing machines of k alternations, which is a nontrivial refinement of Ruzzos circuit characterization of alternating Turing machines. Complete languages in strong sense for each level of the log-time hierarchy are presented, refining a result by Buss. The class GC(s(n), IIBk) is investigated, which is the class of languages accepted by log-time alternating Turing machines of k alternations enhanced by an extra ability of guessing a string of length s(n). A systematic technique is developed to show that for many functions a(n) and for every integer k > 1, the class GC(s(n), IIBk) has natural complete languages. Connections of these results to computational optimization problems are exhibited.
