Turing machines with few accepting computations and low sets for PP

DOI10.1016/0022-0000(92)90022-BzbMath0757.68056OpenAlexW2178192088MaRDI QIDQ1190987

Seinosuke Toda, Johannes Köbler, Uwe Schoening, Jacobo Toran

Publication date: 27 September 1992

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0022-0000(92)90022-b

zbMATH Keywords

relativizationlow setspath restricted nondeterministic polynomial time machines

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (14)

Universally serializable computation ⋮ Isolation, matching, and counting uniform and nonuniform upper bounds ⋮ UP and the low and high hierarchies: A relativized separation ⋮ Graph isomorphism is low for PP ⋮ Quantum and classical complexity classes: Separations, collapses, and closure properties ⋮ Lower bounds and the hardness of counting properties ⋮ Graph Isomorphism is in SPP ⋮ UP and the low and high hierarchies: A relativized separation ⋮ Monotonous and randomized reductions to sparse sets ⋮ Graph isomorphism is low for PP ⋮ A second step towards complexity-theoretic analogs of Rice's Theorem ⋮ Tally NP sets and easy census functions. ⋮ Restrictive Acceptance Suffices for Equivalence Problems ⋮ Gap-definable counting classes

Cites Work

• Unnamed Item
• The complexity of computing the permanent
• A low and a high hierarchy within NP
• The complexity of combinatorial problems with succinct input representation
• Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
• Restricted relativizations of probabilistic polynomial time
• Relative complexity of checking and evaluating
• Complexity of Presburger arithmetic with fixed quantifier dimension
• The polynomial-time hierarchy and sparse oracles
• On Circuit-Size Complexity and the Low Hierarchy in NP
• Quantitative Relativizations of Complexity Classes
• Computational Complexity of Probabilistic Turing Machines
• A decisive characterization of BPP
• On the power of parity polynomial time

This page was built for publication: Turing machines with few accepting computations and low sets for PP