Restrictive Acceptance Suffices for Equivalence Problems

DOI10.1112/S146115700000022XMaRDI QIDQ4504964zbMATH OpenOpenAlexFDO

Authors Lane A. Hemaspaandra, Jörg Rothe, Bernd Borchert

Publication date 25 September 2000

Published in LMS Journal of Computation and Mathematics (Search for Journal in Brave)

Full work available at URL http://www.lms.ac.uk/jcm/3/lms1999-012/

zbMATH Keywords

NP problem

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• scientific article; zbMATH DE number 1390058
• scientific article; zbMATH DE number 874695
• Promise problems complete for complexity classes
• On the restricted equivalence for subclasses of propositional logic
• Quantitative Relativizations of Complexity Classes

Cites work

• A relationship between difference hierarchies and relativized polynomial hierarchies
• BANISHING ROBUST TURING COMPLETENESS
• Complexity Measures for Public-Key Cryptosystems
• Computation times of NP sets of different densities
• Counting classes: Thresholds, parity, mods, and fewness
• Gap-definable counting classes
• Group-theoretic algorithms and graph isomorphism
• scientific article; zbMATH DE number 3594626 (Why is no real title available?)
• scientific article; zbMATH DE number 477971 (Why is no real title available?)
• scientific article; zbMATH DE number 1088264 (Why is no real title available?)
• scientific article; zbMATH DE number 1390058 (Why is no real title available?)
• Isomorphism of graphs of bounded valence can be tested in polynomial time
• On the computational complexity of some classical equivalence relations on boolean functions
• On the power of parity polynomial time
• On the unique satisfiability problem
• P-Printable Sets
• Probabilistic complexity classes and lowness
• Relative complexity of checking and evaluating
• The complexity of combinatorial problems with succinct input representation
• Turing machines with few accepting computations and low sets for PP
• Unambiguous Computation: Boolean Hierarchies and Sparse Turing-Complete Sets
• Upward separation for FewP and related classes

Cited in

(3)

• scientific article; zbMATH DE number 1390058 (Why is no real title available?)
• Gaps, ambiguity, and establishing complexity-class containments via iterative constant-setting
• Lower bounds and the hardness of counting properties

This page was built for publication: Restrictive Acceptance Suffices for Equivalence Problems

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