💻 computer science

Algebraic Circuits Over Sum and Shift and Existential Presburger Arithmetic with Divisibility

This paper proves that the satisfiability problem for existential Presburger arithmetic with divisibility (EPAD) is PP-hard, thereby refuting the long-standing conjecture that it lies in NP, by reducing it from a threshold coefficient problem for arithmetic circuits over addition and shifts.

Original authors: Ignacio Barros, Michaël Cadilhac, Guillermo A. Pérez

Published 2026-06-15

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Ignacio Barros, Michaël Cadilhac, Guillermo A. Pérez

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a detective trying to solve a massive logic puzzle. The puzzle involves numbers, addition, and a special rule called "divisibility" (asking if one number divides another evenly). For decades, computer scientists believed this puzzle was hard, but not impossible hard—they thought a smart computer could solve it in a reasonable amount of time (a complexity class called NP).

This paper is like a detective shouting, "Wait a minute! That puzzle is actually much harder than we thought!" The authors prove that solving this specific type of math puzzle is actually as difficult as the hardest counting problems known to science (a class called PP). If they are right, it means the old belief was wrong, and these puzzles are exponentially harder than anyone expected.

Here is how they did it, explained through everyday analogies:

1. The "Magic Machine" (Sum-Shift Circuits)

To prove their point, the authors built a special, simplified machine. Think of it as a LEGO factory.

Normal factories can take two piles of bricks and smash them together to make something new (multiplication).
This factory is very restricted. It can only stack piles (addition) or slide a whole pile to a new shelf (shifting). It cannot smash piles together.

Even with these tiny, boring rules, the authors showed that if you arrange the LEGO bricks just right, this factory can count incredibly complex things. They proved that asking "How many ways can this factory build a specific tower?" is a super-hard math problem.

2. The "Translator" (The Reduction)

The authors then built a translator that turns the LEGO factory's instructions into the "Divisibility Puzzle."

They found a way to make the LEGO factory's "sliding" action look like a divisibility rule in the puzzle.
They showed that if you can solve the Divisibility Puzzle, you can also solve the LEGO factory's counting problem.
Since the LEGO counting problem is known to be super-hard, the Divisibility Puzzle must be super-hard too.

3. The "Magic Multiplier" (The Scaling Gadget)

The secret sauce in their translator is a clever trick they call a Scaling Gadget.
Imagine you have a magic rule that says: "If you have a number $u$ , you must also have a number $v$ that is exactly $2^{2^j} + 1$ times bigger than $u$ ."

For a small $j$ , this isn't a big deal. But as $j$ gets bigger, that multiplier becomes astronomically huge.

If $j=10$ , the multiplier is a number with thousands of digits.
The authors proved that to write down this rule in the puzzle, you don't need a long list of instructions. You can do it with a short, neat set of rules.
The Catch: Even though the instructions are short, the numbers inside them are gigantic. It's like having a recipe that says "Add 1 cup of flour" but the "cup" is actually the size of the entire Earth.

4. The "Explosion" (Why Old Methods Fail)

For years, mathematicians tried to solve these puzzles by simplifying them. They had a method called Normalization, which is like trying to tidy up a messy room by grouping similar items together.

The hope was that you could tidy up the room until everything was small and manageable.
The authors showed that with their "Magic Multiplier" trick, every time you try to tidy up the room, the items you group together become gigantic.
Instead of getting a neat, small list of rules, you end up with a single rule containing a number so huge it would take more space than the entire internet to write down.

The Big Takeaway

The paper delivers two main blows to the old way of thinking:

The Puzzle is Harder: The "Divisibility Puzzle" is not just hard; it belongs to a much tougher category of problems. Unless a major mathematical miracle happens (where a class of problems called NP turns out to be the same as PP), we cannot solve these puzzles quickly.
Simplification Fails: You cannot simply "clean up" these puzzles to make them easy. The act of cleaning them up forces the numbers to explode in size, making the problem just as hard as the original.

In short: The authors built a tiny, restricted machine that counts incredibly hard things, translated that machine into a divisibility puzzle, and showed that trying to simplify that puzzle only makes the numbers inside it grow to impossible sizes. This proves the puzzle is fundamentally, intractably difficult.

Technical Summary: Algebraic Circuits Over Sum and Shift and Existential Presburger Arithmetic with Divisibility

Problem Statement
The paper investigates the computational complexity of Existential Presburger Arithmetic with Divisibility (EPAD). While standard existential Presburger arithmetic is known to be NP-complete, the addition of divisibility predicates ( $f(x) \mid g(x)$ ) significantly alters the landscape. Although the satisfiability problem for EPAD has long been known to be NP-hard, a prevailing "folklore" belief suggested it might reside within NP. This paper challenges that expectation by establishing a stronger lower bound.

Methodology
The authors employ a reduction from a specific counting problem defined over a restricted arithmetic circuit model to the satisfiability of EPAD formulas. The methodology proceeds in three main stages:

Sum-Shift Circuits and Coefficients: The authors define a restricted model of arithmetic circuits called sum-shift circuits. These circuits operate over polynomials using only addition gates and "shift" gates (multiplication by monomials $x^a$ ), but they lack general multiplication gates. The only source of succinctness is the sharing of subcircuits. They define the Coeff problem: computing the coefficient of a specific monomial $x^t$ in the polynomial computed by such a circuit. They prove that the threshold variant, Coeff-LT (determining if the coefficient is less than a given $K$ ), is PP-complete. This relies on the fact that sum-shift circuits can succinctly represent the generating function for the subset-sum problem, $\prod (1 + x^{a_i})$ .
Reduction to EPAD via Divisibility Gadgets: The authors reduce Coeff-LT to EPAD satisfiability. The reduction evaluates the circuit at a large base $B = 2^b$ . In this encoding:
- Addition gates become linear equalities.
- Shift gates ( $x^a$ ) are simulated by polynomial-size systems of linear divisibility constraints that enforce multiplication by $2^a$ .
- Crucially, they construct scaling gadgets that force specific multiplicative relations between variables, such as $v = (2^{2^j} + 1)u$ . These gadgets utilize the merge-absorptive property, a specific structural fragment of EPAD.
Analysis of Normalization and Coefficient Blow-up: The paper analyzes the behavior of normalization procedures (specifically Kernel Normal Form, or KNF) on these constructed systems. They demonstrate that while the input systems are small (polynomial size), any normalization step that records the forced multiplicative relation (e.g., $v = F_j u$ where $F_j = 2^{2^j} + 1$ ) as a single primitive equation must introduce coefficients of exponential bit-size ( $\Theta(2^j)$ ).

Key Contributions

PP-Hardness of EPAD: The primary result is that EPAD satisfiability is PP-hard. This rules out the possibility that EPAD is in NP unless $\text{NP} = \text{PP}$ .
Merge-Absorptive Fragment: The authors define a polynomial-time recognizable fragment of EPAD called merge-absorptive. Systems in this fragment allow for a "finite-quotient simplification" where divisibility atoms are replaced by finite disjunctions of equations. They prove that EPAD satisfiability remains PP-hard even when restricted to this fully simplifiable fragment.
Sum-Shift Circuit Complexity: The paper establishes that the coefficient problem for sum-shift circuits is #P-complete and its threshold version is PP-complete. This provides a new, restricted algebraic model for hardness proofs.
Normalization Obstruction: The paper clarifies the limitations of normalization strategies. It shows that the obstruction to placing EPAD in NP is twofold:
1. The counting lower bound (PP-hardness) implies that even if normalization produced a polynomial number of branches, the resulting problem would still be PP-hard.
2. The coefficients in the normalized equations themselves can blow up to exponential size, preventing a polynomial-size representation of the normalized form.

Results

Theorem 20: EPAD-SAT is PP-hard under polynomial-time many-one reductions. This lower bound holds even for the satisfiability of merge-absorptive positive homogeneous linear divisibility systems with declared strict order constraints.
Theorem 30: For the family of scaling gadgets $\Gamma_j$ , any repair step (in either substitution-based Lipshitz normalization or the KNF framework) that exposes the forced endpoint relation $v = (2^{2^j} + 1)u$ via a primitive affine equation must produce a coefficient of bit-size $\Theta(2^j)$ .
Corollary for String Constraints: The authors note that their lower bound implies that the satisfiability problem for positive Boolean combinations of word equations and length constraints is also PP-hard, extending previous work by Day and Konefal.

Significance and Claims
The paper claims to provide the first improvement over the long-standing NP-hard lower bound for EPAD satisfiability. It explicitly refutes the folklore belief that EPAD lies in NP.

The significance lies in identifying a specific arithmetic mechanism—the ability of sum-shift circuits to generate double-exponential multipliers via divisibility constraints—that drives the complexity. The authors argue that the difficulty is not merely a lack of a clever algorithm but is inherent to the structure of the problem:

Complexity-Theoretic Barrier: The problem is intrinsically harder than NP (unless $\text{NP} = \text{PP}$ ).
Representation Barrier: Even if one attempts to simplify the system via normalization, the coefficients required to represent the solution space explode in size, preventing a compact representation.

The paper concludes that the counting lower bound, the existence of a fully simplifiable fragment that remains hard, and the normalization coefficient blow-up all stem from the same underlying arithmetic mechanism. It does not propose new algorithms for solving EPAD but rather delineates the theoretical limits of such approaches.