scientific article; zbMATH DE number 4007722

MaRDI QIDQ3757396zbMATH OpenFDO

Authors Ingo Wegener

Publication date 1987

zbMATH Keywords

lower boundsBoolean circuitsBoolean functionscircuit complexitybranching programsdecision tree complexity of clique functions

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Recommendations

• On the complexity of branching programs and decision trees for clique functions
• scientific article; zbMATH DE number 3919835
• A read-once lower bound and a \((1,+k)\)-hierarchy for branching programs
• scientific article; zbMATH DE number 3913677
• scientific article; zbMATH DE number 1361505

Cited in

(6)

• Time-space trade-offs for branching programs
• On the complexity of branching programs and decision trees for clique functions
• scientific article; zbMATH DE number 3919835 (Why is no real title available?)
• On P versus NP\(\cap\)co-NP for decision trees and read-once branching programs
• scientific article; zbMATH DE number 1400211 (Why is no real title available?)
• Entropy of contact circuits and lower bounds on their complexity

This page was built for publication:

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