Boolean matrix product with few negations #
Every monotone circuit for the Boolean product of two n × n matrices has at
least n ^ 3 AND gates (Algebraic.Monotone.MatrixProduct.cube_le_andCost),
while circuits with negations compute it with O(n ^ ω) gates through integer
matrix multiplication. This file interpolates between the two by the number of
negations.
The circuit model is the imported library's De Morgan signature
(DeMorgan.signature: the constants, identity, NOT, and fan-in-two AND and OR,
with unbounded fan-out). NOT gates are counted by DeMorgan.notCost and AND
gates by DeMorgan.andCost; every gate of the program is counted, used or not,
and OR gates, constants and identities are free. With no NOT gate the model is
that of Algebraic.Monotone.MatrixProduct.card_le_andCost (monotone circuits
with constants), and it contains the AND/OR circuits of cube_le_andCost.
Main results #
div_mul_div_mul_le_andCost: a circuit with at mosttNOT gates computing the product of anI × Kmatrix and aK × Jmatrix has at least⌊I / 2 ^ t⌋ * ⌊J / 2 ^ t⌋ * KAND gates; fort = 0this is the monotone boundI * J * K.mul_div_sq_le_andCost: in the square case,n * ⌊n / 2 ^ t⌋ ^ 2AND gates.cube_le_four_pow_mul_andCost: if2 ^ t ≤ n, thenn ^ 3 ≤ 4 ^ (t + 1) * #AND.mul_logb_sub_one_lt_notCost: a circuit with fewer thann ^ (3 - ε)AND gates,ε ≤ 2, has more than(ε / 2) * log₂ n - 1NOT gates.mul_mul_le_andCost_add,cube_sub_le_andCost: if every NOT gate computes a function of the inputs in a fixed setS, the circuit has at leastI * J * K - |S| * max I JAND gates,n ^ 3 - |S| * nin the square case.mul_mul_le_andCost_add_of_monotone_or_dependsOnlyOn,cube_sub_le_andCost_of_monotone_or_dependsOnlyOn: the same bounds when every gate computing a non-monotone function depends only on the inputs inS; then so does every NOT gate.
Proof #
The first NOT gate reads a monotone function h of the inputs. Split the rows
of x and the columns of y into halves and evaluate h on the assignment
that is one exactly on the first halves. If it is zero, h vanishes once the
second halves are set to zero; if it is one, h is one once the first halves
are set to one. Either way the NOT gate becomes constant, and the product of
the remaining halves is still computed, since an entry of the product reads
only its own row and column. Replacing the NOT gate by its constant and the
fixed inputs by constants gives a circuit with one NOT gate fewer, the same AND
gates, and half the rows and columns. After t steps the monotone bound for
circuits with constants applies. If instead every NOT gate depends only on the
inputs in S, setting those to zero makes every NOT gate constant at once and
leaves a monotone circuit for the partial product over the triples that avoid
S. The proofs are in
Complexitylib.Algebraic.LowerBound.Monotone.MatrixProduct.NegationLimited.Internal.
Prior art #
No lower bound for the Boolean matrix product by circuits with a bounded number
of NOT gates appears in the literature we know. The monotone bound n ^ 3 is
due to Pratt (1975), Paterson (1975) and Mehlhorn--Galil (1976). Markov (1958)
and Fischer (1975) show that ⌈log₂ (N + 1)⌉ NOT gates suffice for every
function of N inputs, with polynomial overhead in Fischer's construction.
Jukna (Information Processing Letters, 2004) uses a similar direct-sum
restriction for an explicit multi-output function needing
log n - O(log log n) NOT gates.
Boolean matrix product with few negations. Place entry (i, k) of an
I × K matrix at input x i k and entry (k, j) of a K × J matrix at input
y k j, all at distinct inputs. A De Morgan circuit with at most t NOT gates
whose output z i j computes ⋁ k, x i k ∧ y k j for every i and j has at
least ⌊I / 2 ^ t⌋ * ⌊J / 2 ^ t⌋ * K AND gates.
Square Boolean matrix product with few negations. A De Morgan circuit
with at most t NOT gates computing the Boolean product of two n × n
matrices, in the row-major layout of cube_le_andCost, has at least
n * ⌊n / 2 ^ t⌋ ^ 2 AND gates.
Negations needed for a sub-cubic product. If a De Morgan circuit with at
most t NOT gates computes the Boolean product of two n × n matrices and
2 ^ t ≤ n, then n ^ 3 ≤ 4 ^ (t + 1) * #AND. Equivalently, a circuit with
fewer than n ^ 3 / 4 ^ (t + 1) AND gates has more than t NOT gates, or
n < 2 ^ t.
Boolean matrix product with negations of few variables. Place the
entries of an I × K matrix and a K × J matrix at distinct inputs of a De
Morgan circuit whose output z i j computes ⋁ k, x i k ∧ y k j for every i
and j. If every NOT gate computes a function of the inputs in S, the
circuit has at least I * J * K - |S| * max I J AND gates.
Square Boolean matrix product with negations of few variables. If every
NOT gate of a De Morgan circuit computing the Boolean product of two n × n
matrices, in the row-major layout of cube_le_andCost, computes a function of
the inputs in S, the circuit has at least n ^ 3 - |S| * n AND gates.
Boolean matrix product with non-monotone gates of few variables. If
every gate of a De Morgan circuit computing the product of an I × K matrix and
a K × J matrix, laid out at distinct inputs, computes a monotone function or a
function of the inputs in S, the circuit has at least
I * J * K - |S| * max I J AND gates.
Square Boolean matrix product with non-monotone gates of few variables.
If every gate of a De Morgan circuit computing the Boolean product of two
n × n matrices, in the row-major layout of cube_le_andCost, computes a
monotone function or a function of the inputs in S, the circuit has at least
n ^ 3 - |S| * n AND gates.
Negations needed for a sub-cubic product, logarithmic form. If a De
Morgan circuit computing the Boolean product of two n × n matrices, n ≥ 1,
in the row-major layout of cube_le_andCost, has fewer than n ^ (3 - ε) AND
gates for some ε ≤ 2, then it has more than (ε / 2) * log₂ n - 1 NOT
gates.