On counting problems and the polynomial-time hierarchy

DOI10.1016/0304-3975(80)90027-4zbMath0499.68020OpenAlexW2020831804MaRDI QIDQ1171880

Dana Angluin

Publication date: 1980

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

Full work available at URL: https://doi.org/10.1016/0304-3975(80)90027-4

zbMATH Keywords

probabilistic Turing machine with oracleranked oracle property

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15)

Related Items

Nonlevelable sets and immune sets in the accepting density hierarchy inNP ⋮ The complexity of combinatorial problems with succinct input representation ⋮ Some observations on the connection between counting and recursion ⋮ Phase transitions of PP-complete satisfiability problems ⋮ Relativized alternation and space-bounded computation ⋮ Probabilistic quantifiers and games ⋮ Graph isomorphism is in the low hierarchy ⋮ A refinement of the low and high hierarchies ⋮ Bounded query machines: on NP( ) and NPQUERY( ) ⋮ On a theorem of Razborov ⋮ On the complexity of ranking ⋮ Restricted relativizations of probabilistic polynomial time ⋮ Polynomial-time 1-Turing reductions from \(\#\)PH to \(\#\)P ⋮ Parity, circuits, and the polynomial-time hierarchy ⋮ A uniform approach to define complexity classes ⋮ UP and the low and high hierarchies: A relativized separation ⋮ Enumerative counting is hard ⋮ Generix strikes again ⋮ Graph isomorphism problem ⋮ Nonerasing, counting, and majority over the linear time hierarchy ⋮ On some natural complete operators

Cites Work

• Unnamed Item
• The complexity of computing the permanent
• The polynomial-time hierarchy
• Complete sets and the polynomial-time hierarchy
• A note on the graph isomorphism counting problem
• A second step toward the polynomial hierarchy
• The Complexity of Enumeration and Reliability Problems
• Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
• Computational Complexity of Probabilistic Turing Machines
• Erratum: A Fast Monte-Carlo Test for Primality
• Relativized questions involving probabilistic algorithms