To understand why modern automated reasoners—such as SAT solvers or Integer Linear Programming (ILP) solvers—struggle to scale across multiple processors, we must look at the structural "shape" of the proofs they generate.
A logical proof can be viewed as a graph of inferences. The size of the proof is the total number of logical steps taken, which represents the total computational work. The depth of the proof is the length of the longest chain of sequential dependencies. Depth represents the minimum time required to complete the proof, even if we had an infinite number of parallel processors available.
The Parallelization Bottleneck
When we attempt to parallelize a solver, we hope that adding more computational cores will divide the total work evenly. However, as shown in Resolution and Parallelizability: Barriers to the Efficient Parallelization of SAT Solvers, the maximum theoretical speedup in parallel SAT solving is strictly bounded by the ratio of total logical steps to the depth of the longest dependency chain.
Katsirelos et al. (2013) demonstrated that logical proofs generated by conflict-driven solvers frequently contain structural bottlenecks—deep, narrow sections where the number of independent clauses available for derivation drops to a minimum. At these bottleneck points, a single critical inference step must be completed before any subsequent work can proceed. No matter how many thousands of cores are available, parallel processors are forced to remain idle while waiting for that single sequential step to finish. This structural property explains why certain problem domains, such as cryptography, exhibit an inherent sequentiality that resists massive parallelization.
The Price of Short Proofs: Supercritical Tradeoffs
A natural intuition might suggest that if we can find a way to make proofs shorter (minimizing their size), they will inherently become easier to compute and faster to resolve. However, research into proof complexity reveals a counterintuitive phenomenon known as a supercritical tradeoff, where restricting a proof's size forces its depth to explode.
In Extremely Deep Proofs, Fleming et al. (2022) analyzed fundamental proof systems like Resolution and Cutting Planes to understand how restricting proof size impacts depth. The authors discovered that restricting a proof's size below a certain threshold forces the proof depth to exceed trivial worst-case bounds. This "supercritical" behavior means that achieving a short proof necessitates a structure that is inherently deep and highly sequential. If an algorithm minimizes proof size, it may inadvertently force the proof depth to become exponentially large, making the underlying computational problem difficult to parallelize.
This limitation extends beyond propositional logic into geometric reasoning. In On the Power and Limitations of Branch and Cut, Fleming et al. (2021) explored the fundamental power of algorithms used to solve Integer Linear Programming (ILP) by bridging top-down branching and bottom-up deduction. The authors demonstrated that even when an ILP problem admits a short proof, it may require a sequential depth that is prohibitively large. Understanding these supercritical tradeoffs is essential for identifying problems that are inherently resistant to parallelization or efficient depth-limited reasoning.
Universality Across Stronger Proof Systems
Does this bottleneck disappear if we use more powerful logical frameworks? To answer this, Itsykson et al. (2026) investigated Resolution over Parities ($\text{Res}(\oplus)$), a powerful proof system capable of reasoning with parity operations.
In Supercritical Tradeoff Between Size and Depth for Resolution over Parities, the authors established that certain formulas force a fundamental limit on the balance between size and depth. Specifically, any refutation in the $\text{Res}(\oplus)$ system must either be exponentially large or possess a depth that significantly exceeds typical expectations for large proofs. This confirmed that supercriticality is a fundamental structural property of mathematical reasoning rather than an artifact of weaker proof systems, proving that small proofs in these advanced systems still necessitate a disproportionately high, superlinear depth.
Key Foundational Work
Resolution and Parallelizability: Barriers to the Efficient Parallelization of SAT Solvers (2013) — contributed 7 concept elements to this direction.
On the Power and Limitations of Branch and Cut (2021) — contributed 1 concept elements to this direction.