The power of negative thinking in multiplying Boolean matrices. (English) Zbl 0318.94040

It is proved that there are at least \(n^3\) distinct AND-gate inputs in an AND-OR circuit for multiplying two \(n\times n\) Boolean matrices. An AND-NOT circuit for the same purpose requires only \(O(n^{\log_2 7} \cdot \log^2n)\) gates. Hence the complexity gap between AND-OR and AND-OR-NOT realization of monotonic Boolean functions is proved to be larger than was previously known.
Reviewer: N. N. Necula


94C10 Switching theory, application of Boolean algebra; Boolean functions (MSC2010)
68Q25 Analysis of algorithms and problem complexity
Full Text: DOI