scientific article; zbMATH DE number 4047115
From MaRDI portal
Publication:3783568
Recommendations
- The power of nondeterminism in polynomial-size bounded-width branching programs
- Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
- On the hierarchy of nondeterministic branching k-programs
- Comparing the sizes of nondeterministic branching read-k-times programs
- Complexity Theoretical Results on Nondeterministic Graph-driven Read-Once Branching Programs
Cited in
(21)- The power of nondeterminism in polynomial-size bounded-width branching programs
- Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
- Branching programs provide lower bounds on the area of multilective deterministic and nondeterministic VLSI circuits
- Lower bounds for depth-restricted branching programs
- Modified branching programs and their computational power
- Skew circuits of small width
- Circuits on cylinders
- A characterisation of NL/poly via nondeterministic finite automata
- Functions computable by Boolean circuits of logarithmic depth and branching programs of a special type
- scientific article; zbMATH DE number 4172394 (Why is no real title available?)
- Expressibility and Nonuniform Complexity Classes
- scientific article; zbMATH DE number 3954251 (Why is no real title available?)
- PSPACE SURVIVES CONSTANT-WIDTH BOTTLENECKS
- Comparing the sizes of nondeterministic branching read-k-times programs
- scientific article; zbMATH DE number 619536 (Why is no real title available?)
- Complexity Theoretical Results on Nondeterministic Graph-driven Read-Once Branching Programs
- scientific article; zbMATH DE number 1746571 (Why is no real title available?)
- ON SERIALIZABLE LANGUAGES
- Worst Case Branching and Other Measures of Nondeterminism
- Inductive counting for width-restricted branching programs
- Polynomial size \(\Omega\)-branching programs and their computational power
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3783568)
