Algebraic Circuits Over Sum and Shift and Existential Presburger Arithmetic with Divisibility (opens in new tab)

We study existential Presburger arithmetic extended with divisibility predicates (EPAD). Its satisfiability problem has long been known to be NP-hard, and has often been expected to lie in NP. We prove that it is PP-hard, ruling out this expectation unless NP=PP. This also implies \PP-hardness of satisfiability for positive Boolean combinations of word equations and length constraints. The lower bound is compatible with a strong form of Lipshitz...