Restricted relativizations of probabilistic polynomial time

DOI10.1016/0304-3975(92)90333-BzbMath0749.68038MaRDI QIDQ1186606

Seinosuke Toda

Publication date: 28 June 1992

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

zbMATH Keywords

relativizationprobabilistic polynomial time

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

Turing machines with few accepting computations and low sets for PP

Cites Work

• The complexity of computing the permanent
• The complexity of combinatorial problems with succinct input representation
• Bounded query machines: on NP and PSPACE
• On counting problems and the polynomial-time hierarchy
• The polynomial-time hierarchy
• Complete sets and the polynomial-time hierarchy
• A second step toward the polynomial hierarchy
• The polynomial-time hierarchy and sparse oracles
• On Circuit-Size Complexity and the Low Hierarchy in NP
• On Restricting the Size of Oracles Compared with Restricting Access to Oracles
• The Complexity of Enumeration and Reliability Problems
• Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
• Computational Complexity of Probabilistic Turing Machines