Complexity classes defined by counting quantifiers
Author:
Open Access
- 1 July 1991
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 38 (3) , 752-773
Abstract
:We study the polynomial time counting hierarchy, a hierarchy of complexity classes relatedto the notion of counting. We investigate some of their structural properties, settling manyopen questions dealing with oracle characterizations, closure under boolean operations,and relations with other complexity classes. We develop a new combinatorial techniqueto obtain relativized separations for some of the studied classes, which imply absoluteseparations for some logarithmic time bounded...Keywords
This publication has 9 references indexed in Scilit:
- The complexity of combinatorial problems with succinct input representationActa Informatica, 1986
- Parity, circuits, and the polynomial-time hierarchyTheory of Computing Systems, 1984
- Games against nature1983
- Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1SIAM Journal on Computing, 1981
- AlternationJournal of the ACM, 1981
- On counting problems and the polynomial-time hierarchyTheoretical Computer Science, 1980
- Computational Complexity of Probabilistic Turing MachinesSIAM Journal on Computing, 1977
- Complete sets and the polynomial-time hierarchyTheoretical Computer Science, 1976
- The polynomial-time hierarchyTheoretical Computer Science, 1976