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

zbMATH Open1249.68079MaRDI QIDQ3115642FDOQ3115642

Authors: Alexander V. Vasiliev 

Publication date: 10 February 2012

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

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)

Cited In (1)

• Title not available (Why is that?)

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)