Unambiguous Computation: Boolean Hierarchies and Sparse Turing-Complete Sets

DOI10.1137/S0097539794261970MaRDI QIDQ4337649zbMATH OpenOpenAlexFDO

Authors Lane A. Hemaspaandra, Jörg Rothe

Publication date 26 May 1997

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/s0097539794261970

zbMATH Keywords

Boolean hierarchyunambiguous computationsparse Turing-complete sets

Mathematics Subject Classification ID

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

Recommendations

• Hierarchical Unambiguity
• Some consequences of non-uniform conditions on uniform classes
• \(P^{NP[O(\log n)]}\) and sparse turing-complete sets for NP
• Hierarchical Unambiguity
• On the probabilistic closure of the loose unambiguous hierarchy

Cited in

(10)

• Restrictive Acceptance Suffices for Equivalence Problems
• Universally serializable computation
• On the probabilistic closure of the loose unambiguous hierarchy
• Unambiguous computations and locally definable acceptance types
• Intersection suffices for Boolean hierarchy equivalence
• A Downward Collapse within the Polynomial Hierarchy
• A downward translation in the polynomial hierarchy
• Query Order
• Exact complexity of exact-four-colorability
• Tally NP sets and easy census functions.

This page was built for publication: Unambiguous Computation: Boolean Hierarchies and Sparse Turing-Complete Sets

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