An impossibility gap between width-4 and width-5 permutation branching programs

DOI10.1016/j.ipl.2005.01.012zbMath1182.68101OpenAlexW2090852992MaRDI QIDQ1041742

Alex Brodsky

Publication date: 4 December 2009

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2005.01.012

zbMATH Keywords

computational complexityformal languagesbranching programs

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Theory of software (68N99)

Related Items (2)

Skew Circuits of Small Width ⋮ Skew circuits of small width

Cites Work

• Unnamed Item
• Unnamed Item
• Non-uniform automata over groups
• Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
• Finite soluble groups
• Superlinear lower bounds for bounded-width branching programs
• Finite monoids and the fine structure of NC ¹
• A Property of Finite Simple Non-Abelian Groups

This page was built for publication: An impossibility gap between width-4 and width-5 permutation branching programs