New lower bounds and hierarchy results for restricted branching programs

DOI10.1006/jcss.1996.0050zbMath0859.68027OpenAlexW1972837379MaRDI QIDQ1816743

Detlef Sieling

Publication date: 13 March 1997

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/jcss.1996.0050

zbMATH Keywords

unrestricted branching programs

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (4)

Expanders and time-restricted branching programs ⋮ Neither reading few bits twice nor reading illegally helps much ⋮ A lower bound on branching programs reading some bits twice ⋮ A read-once lower bound and a \((1,+k)\)-hierarchy for branching programs

This page was built for publication: New lower bounds and hierarchy results for restricted branching programs