Using inductive counting to simulate nondeterministic computation

DOI10.1006/inco.1993.1004zbMath0769.68028OpenAlexW2072909619MaRDI QIDQ1207953

Dirk Siefkes, Gerhard Buntrock, Hemaspaandra, Lane A.

Publication date: 16 May 1993

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/inco.1993.1004

zbMATH Keywords

cost of simulating nondeterminism with Valiant's paradigm of unique computationinductive counting

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

Collapsing degrees via strong computation ⋮ Unambiguous computations and locally definable acceptance types ⋮ On the power of unambiguity in log-space ⋮ Fault-tolerance and complexity (Extended abstract) ⋮ \textsc{ReachFewL} = \textsc{ReachUL} ⋮ A variant of inductive counting