A lower bound on complexity of branching programs
- 1 January 1984
- book chapter
- Published by Springer Science and Business Media LLC
- p. 480-489
- https://doi.org/10.1007/bfb0030331
Abstract
No abstract availableKeywords
This publication has 6 references indexed in Scilit:
- Bounds for Hodes - Specker theoremLecture Notes in Computer Science, 1984
- ∑11-Formulae on finite structuresAnnals of Pure and Applied Logic, 1983
- Bounds for width two branching programsPublished by Association for Computing Machinery (ACM) ,1983
- $\Omega (n\log n)$ Lower Bounds on Length of Boolean FormulasSIAM Journal on Computing, 1982
- Parity, circuits, and the polynomial-time hierarchyPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1981
- Lengths of Formulas and Elimination of Quantifiers IPublished by Elsevier BV ,1968