Short Presburger arithmetic is hard

2017/08/28 by Danny Nguyen, Nguyen, Danny, Igor Pak +1
Computer Science · #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics #Logic (math.LO) #Logic in Computer Science (cs.LO) #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.1708.08179

openalex publication_date 2017/08/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We study the computational complexity of short sentences in Presburger arithmetic (Short-PA). Here by "short" we mean sentences with a bounded number of variables, quantifiers, inequalities and Boolean operations; the input consists only of the integer coefficients involved in the linear inequalities. We prove that satisfiability of Short-PA sentences with m+2 alternating quantifiers is Σ_P^m-complete or Π_P^m-complete, when the first quantifier is ∃ or ∀, respectively. Counting versions and restricted systems are also analyzed. Further application are given to hardness of two natural problems in Integer Optimizations.

Related

• Complexity of short Presburger arithmetic
• Parametric Presburger Arithmetic: Complexity of Counting and Quantifier Elimination
• An efficient quantifier elimination procedure for Presburger arithmetic
• The complexity of Presburger arithmetic with power or powers
• The Universal Fragment of Presburger Arithmetic with Unary Uninterpreted Predicates is Undecidable