The power of nondeterminism in polynomial-size bounded-width branching programs

DOI10.1016/0304-3975(88)90073-4zbMath0665.68041OpenAlexW1964528982MaRDI QIDQ1116338

Christoph Meinel

Publication date: 1988

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(88)90073-4

zbMATH Keywords

nondeterminismbranching programsnonuniform complexity classes

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15)

Cites Work

• Reducibility by algebraic projections
• Relationships between nondeterministic and deterministic tape complexities
• Unnamed Item
• Unnamed Item

This page was built for publication: The power of nondeterminism in polynomial-size bounded-width branching programs