Determinism, Nondeterminism, Alternation, and Counting

Sanjay Gupta (Department of Computer Science, Virginia Polytechnic Institute and State University, USA)

Abstract: Toda proved a remarkable connection between the polynomial hierarchy and the counting classes. Tarui improved Toda s result to show the connection to a weak form of counting and provided an elegant proof. This paper shows that a key step in Tarui s proof can be done uniformly using the depth-first traversal and provides the algorithm that generalizes Toda s result to arbitrary alternating Turing machines (ATMs). Tarui s proof is carefully dissected to obtain an interesting relationship between the running time of the constructed counting machine and the diffeerent parameters of the original ATM: the number of alternation blocks, the number of non-deterministic steps, and the number of deterministic steps.

Keywords: alternating Turing machines, computational complexity, counting classes, theory of computation

Categories: F.1