scientific article; zbMATH DE number 4045650

MaRDI QIDQ3783219zbMATH OpenFDO

Authors Pavel Pudlák

Publication date 1987

zbMATH Keywords

Boolean circuitsBoolean formulabranching programcomplexity measuresdirected switching networklower boundsTuring machine complexityundirected switching network

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Recommendations

• The Boolean Hierarchy I: Structural Properties
• The Boolean Hierarchy II: Applications
• scientific article; zbMATH DE number 3988706
• The complexity hierarchy of Boolean bases
• Circuits, computers, and beyond Boolean logic
• On circuit functionality in Boolean networks
• Boolean circuits versus arithmetic circuits
• The size and depth of layered Boolean circuits
• The size and depth of layered Boolean circuits
• scientific article; zbMATH DE number 4204280

Cited in

(14)

• Nearly optimal hierarchies for network and formula size
• An improved complexity hierarchy on the depth of Boolean functions
• Lower bounds of the complexity of symmetric Boolean functions of contact- rectifier circuits
• On almost bad Boolean bases
• Separating OR, SUM, and XOR circuits
• Branching Programs for Tree Evaluation
• scientific article; zbMATH DE number 4204280 (Why is no real title available?)
• The Boolean Hierarchy II: Applications
• scientific article; zbMATH DE number 61460 (Why is no real title available?)
• Comparing the sizes of nondeterministic branching read-k-times programs
• Cyclic Boolean circuits
• What circuit classes can be learned with non-trivial savings?
• Fine hierarchies and Boolean terms
• Pebbles and branching programs for tree evaluation

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 Q3783219)