Determinism, Nondeterminism, Alternation, and Counting
Sanjay Gupta · OhioLink ETD Center (Ohio Library and Information Network) · 2020
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 different parameters of the original ATM: the number of alternation blocks, the number of nondeterministic steps, and the number of deterministic steps.