Using inductive counting to simulate nondeterministic computation

DOI10.1006/INCO.1993.1004MaRDI QIDQ1207953zbMATH OpenOpenAlexFDO

Authors Gerhard Buntrock, Dirk Siefkes, Lane A. Hemaspaandra

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)

Recommendations

• scientific article; zbMATH DE number 18628
• Exact computation of the number of accepting paths of an NTM
• Inductive counting below LOGSPACE
• A variant of inductive counting
• Unambiguous functions in logarithmic space

Cited in

(10)

• Unambiguous computations and locally definable acceptance types
• A variant of inductive counting
• On the power of unambiguity in log-space
• Collapsing degrees via strong computation
• Exact computation of the number of accepting paths of an NTM
• Two Applications of Inductive Counting for Complementation Problems
• scientific article; zbMATH DE number 18628 (Why is no real title available?)
• Fault-tolerance and complexity (extended abstract)
• Inductive counting for width-restricted branching programs
• \textsc{ReachFewL} = \textsc{ReachUL}

This page was built for publication: Using inductive counting to simulate nondeterministic computation

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