Restrictive Acceptance Suffices for Equivalence Problems
From MaRDI portal
Publication:4504964
DOI10.1112/S146115700000022XzbMath0951.68041OpenAlexW2005801770MaRDI QIDQ4504964
Hemaspaandra, Lane A., 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/
Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The complexity of combinatorial problems with succinct input representation
- Group-theoretic algorithms and graph isomorphism
- Isomorphism of graphs of bounded valence can be tested in polynomial time
- Turing machines with few accepting computations and low sets for PP
- Relative complexity of checking and evaluating
- Probabilistic complexity classes and lowness
- On the computational complexity of some classical equivalence relations on boolean functions
- Gap-definable counting classes
- Upward separation for FewP and related classes
- Computation times of NP sets of different densities
- On the unique satisfiability problem
- Complexity Measures for Public-Key Cryptosystems
- BANISHING ROBUST TURING COMPLETENESS
- Unambiguous Computation: Boolean Hierarchies and Sparse Turing-Complete Sets
- P-Printable Sets
- A relationship between difference hierarchies and relativized polynomial hierarchies
- On the power of parity polynomial time
- Counting classes: Thresholds, parity, mods, and fewness
