Determinism, Nondeterminism, Alternation, and Counting

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