Functions computable by Boolean circuits of logarithmic depth and branching programs of a special type

MaRDI QIDQ3115642zbMATH OpenFDO

Authors Alexander V. Vasiliev

Publication date 10 February 2012

zbMATH Keywords

leveled branching programoriented acyclic graph

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
• scientific article; zbMATH DE number 36617
• A read-once lower bound and a \((1,+k)\)-hierarchy for branching programs
• The power of nondeterminism in polynomial-size bounded-width branching programs
• scientific article; zbMATH DE number 4047115

Cited in

(1)

• scientific article; zbMATH DE number 619537 (Why is no real title available?)

This page was built for publication: Functions computable by Boolean circuits of logarithmic depth and branching programs of a special type

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3115642)