Turing machines with few accepting computations and low sets for PP

DOI10.1016/0022-0000(92)90022-BMaRDI QIDQ1190987zbMATH OpenOpenAlexFDO

Authors Johannes Köbler, Uwe Schöning, Jacobo Torán, Seinosuke Toda

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 classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of computation (including implicit computational complexity) (03D15)

Recommendations

• On the power of parity polynomial time
• On the power of parity polynomial time
• scientific article; zbMATH DE number 4213446
• Counting classes: Thresholds, parity, mods, and fewness
• Counting classes: Thresholds, parity, mods, and fewness

Cites work

• scientific article; zbMATH DE number 3799016 (Why is no real title available?)
• A decisive characterization of BPP
• A low and a high hierarchy within NP
• Complexity of Presburger arithmetic with fixed quantifier dimension
• Computational Complexity of Probabilistic Turing Machines
• On Circuit-Size Complexity and the Low Hierarchy in NP
• On the power of parity polynomial time
• Quantitative Relativizations of Complexity Classes
• Relative complexity of checking and evaluating
• Restricted relativizations of probabilistic polynomial time
• Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
• The complexity of combinatorial problems with succinct input representation
• The complexity of computing the permanent
• The polynomial-time hierarchy and sparse oracles

Cited in

(19)

• PP-lowness and a simple definition of AWPP
• \(\mathrm{UP}\) and the low and high hierarchies: a relativized separation
• Lower bounds and the hardness of counting properties
• Tally NP sets and easy census functions.
• scientific article; zbMATH DE number 5354044 (Why is no real title available?)
• A Relatively Small Turing Machine Whose Behavior Is Independent of Set Theory
• A second step towards complexity-theoretic analogs of Rice's Theorem
• Universally serializable computation
• UP and the low and high hierarchies: A relativized separation
• Quantum and classical complexity classes: Separations, collapses, and closure properties
• Gap-definable counting classes
• Isolation, matching, and counting uniform and nonuniform upper bounds
• Graph isomorphism is low for PP
• Graph isomorphism is low for PP
• On the power of parity polynomial time
• Monotonous and randomized reductions to sparse sets
• On the power of parity polynomial time
• Graph Isomorphism is in SPP
• Restrictive Acceptance Suffices for Equivalence Problems

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1190987)