
MON · 2026-11-19 14:36 UTC
Associativity of Multiplication Is Hard for Resolution
The article uses a guest-list puzzle with Alice, Bob and Carol to introduce Boolean Satisfiability (SAT), where a formula of AND/OR/NOT constraints must be made true by some assignment. SAT is NP-complete, yet SAT solvers handle million-variable real-world instances quickly, and are used to verify chip designs and software. Solvers struggle on pigeonhole-principle formulas: Haken proved in 1985 that any resolution proof of them grows exponentially with the number of pigeons, so the article presents proof complexity as the explanation for these limits.
Loading the story on Tree News…