Unambiguous Computation: Boolean Hierarchies and Sparse Turing-Complete Sets

DOI10.1137/S0097539794261970zbMath0870.68070OpenAlexW2072727451MaRDI QIDQ4337649

Jörg Rothe, Hemaspaandra, Lane A.

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 of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (8)

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

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