Unambiguous Computation: Boolean Hierarchies and Sparse Turing-Complete Sets

DOI10.1137/S0097539794261970zbMATH Open0870.68070OpenAlexW2072727451MaRDI QIDQ4337649FDOQ4337649

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

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

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)

Cited In (10)

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

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)