On the complexity of counting in the polynomial hierarchy

DOI10.1016/0304-3975(91)90317-UzbMath0731.68053OpenAlexW2092842790MaRDI QIDQ808260

Marek Piotrów

Publication date: 1991

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(91)90317-u

zbMATH Keywords

countinglower boundOracle alternating Turing machines

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05)

Cites Work

• Unnamed Item
• The complexity of computing the permanent
• \(\Sigma_ 1^ 1\)-formulae on finite structures
• The complexity of facets (and some facets of complexity)
• Logic colloquium '84. Proceedings of the Colloquium held in Manchester, U.K., July 1984
• On bounded query machines
• The polynomial-time hierarchy
• A second step toward the polynomial hierarchy
• Universal classes of hash functions
• Parity, circuits, and the polynomial-time hierarchy
• On Approximation Algorithms for # P

This page was built for publication: On the complexity of counting in the polynomial hierarchy