Go home now Header Background Image
Submission Procedure
share: |
Follow us
Volume 7 / Issue 9

available in:   PDF (137 kB) PS (136 kB)
Similar Docs BibTeX   Write a comment
Links into Future
DOI:   10.3217/jucs-007-09-0816


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