BANISHING ROBUST TURING COMPLETENESS
From MaRDI portal
Publication:4286112
DOI10.1142/S012905419300016XzbMath0802.68049OpenAlexW2030549984MaRDI QIDQ4286112
Sanjay Jain, Hemaspaandra, Lane A., Nikolai K. Vereshchagin
Publication date: 27 April 1994
Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1142/s012905419300016x
polynomial-time reductionsstructural complexityTuring reductionscomplete languagesTuring complete sets
Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items (8)
Intersection suffices for Boolean hierarchy equivalence ⋮ Strong self-reducibility precludes strong immunity ⋮ P-selectivity: Intersections and indices ⋮ The 1-versus-2 queries problem revisited ⋮ LWPP and WPP are not uniformly gap-definable ⋮ Competing provers yield improved Karp-Lipton collapse results ⋮ Error-bounded probabilistic computations between MA and AM ⋮ Restrictive Acceptance Suffices for Equivalence Problems
This page was built for publication: BANISHING ROBUST TURING COMPLETENESS
