Multiplication associativity is provably hard for SAT solvers
Associativity of Multiplication Is Hard for Resolution
Computational ComplexityLogic in Computer Science
Summary
Multiplying numbers is a basic math operation, but computers that solve logical puzzles called SAT solvers struggle to prove that multiplication works the same way no matter how you group numbers (associativity). The authors show that the logical steps needed to prove this are very large and complex, explaining why these solvers perform poorly. They connect this difficulty to another well-known hard logic problem and prove strong limits on how simple any proof can be.
What this means in practice
- •For sat solver developers: Design solver heuristics knowing that multiplication associativity requires inherently large proofs, guiding optimizations away from searching for short resolution proofs in these cases.
- •For hardware verification engineers: Anticipate scalability limits when verifying multipliers by automated theorem provers, using this lower bound to justify when manual intervention or alternative methods are necessary.
A theory result. No direct application yet.
Authors
Vincent Liew
Abstract
SAT solvers are empirically known to perform poorly when reasoning about multiplication. Yet for over a decade we have lacked a theoretical explanation for this phenomenon. CDCL SAT solvers implicitly search for resolution proofs, and no lower bound on proof size has ruled out the existence of short proofs that solvers simply fail to find. We give the first lower bound of this kind by showing that general resolution proofs of the associativity of $n$-bit multiplication require size $2^{Ω((n/\log n)^{1/4})}$. This lower bound holds for a broad class of multiplier encodings based on partial product summation, including the standard array and Wallace-tree multipliers used to bit-blast multiplication in SMT solvers. This result resolves an open problem of Beame and Liew. The proof constructs a reduction from a perfect-matching principle on bounded-degree bipartite expander graphs to multiplier associativity. Itsykson, Slabodkin, and Sokolov proved that this principle is hard for resolution. The lower bound for multiplier associativity follows. The same reduction, when combined with Håstad's recent lower bound for the perfect-matching principle of the odd grid, yields an exponential lower bound for multiplier associativity in the stronger bounded-depth Frege proof systems.