Turing machines with few accepting computations and low sets for PP

DOI10.1016/0022-0000(92)90022-BzbMATH Open0757.68056OpenAlexW2178192088MaRDI QIDQ1190987FDOQ1190987

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

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

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)

Cites Work

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

Cited In (19)

• \(\mathrm{UP}\) and the low and high hierarchies: a relativized separation
• PP-lowness and a simple definition of AWPP
• Title not available (Why is that?)
• Lower bounds and the hardness of counting properties
• Tally NP sets and easy census functions.
• A Relatively Small Turing Machine Whose Behavior Is Independent of Set Theory
• A second step towards complexity-theoretic analogs of Rice's Theorem
• UP and the low and high hierarchies: A relativized separation
• Universally serializable computation
• 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
• On the power of parity polynomial time
• Monotonous and randomized reductions to sparse sets
• Graph isomorphism is low for PP
• On the power of parity polynomial time
• Restrictive Acceptance Suffices for Equivalence Problems
• Graph Isomorphism is in SPP

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)