A lower bound for the computational complexity of a set of disjunctives in a monotone basis

DOI10.1007/BF01404101zbMath0449.94031OpenAlexW1972009093MaRDI QIDQ1147681

Dima Yu. Grigoriev

Publication date: 1981

Published in: Journal of Soviet Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01404101

zbMATH Keywords

circuit complexitymonotone Boolean functionfunctional elementsmonotone basisdisjuntives

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items (1)

Lower bounds in algebraic computational complexity

Cites Work

• Unnamed Item
• The Power of Negative Thinking in Multiplying Boolean Matrices

This page was built for publication: A lower bound for the computational complexity of a set of disjunctives in a monotone basis