Short Presburger Arithmetic Is Hard
From MaRDI portal
Publication:5073520
DOI10.1137/17M1151146WikidataQ126845255 ScholiaQ126845255MaRDI QIDQ5073520
Publication date: 3 May 2022
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1708.08179
Analysis of algorithms and problem complexity (68Q25) Integer programming (90C10) Logic in computer science (03B70) Classical first-order logic (03B10) Complexity of computation (including implicit computational complexity) (03D15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (1)
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Integer points in polyhedra
- Counting integer points in parametric polytopes using Barvinok's rational functions
- Dominoes and the complexity of subclasses of logical theories
- The complexity of Presburger arithmetic with bounded quantifier alternation depth
- Lattice translates of a polytope and the Frobenius problem
- NP-complete decision problems for binary quadratics
- A \(2^{2^{2^{pn}}}\) upper bound on the complexity of Presburger arithmetic
- Complexity of Presburger arithmetic with fixed quantifier dimension
- Counting with rational generating functions
- Minimizing Cubic and Homogeneous Polynomials over Integers in the Plane
- On the Complexity of Nonlinear Mixed-Integer Optimization
- Pareto Optima of Multicriteria Integer Linear Programs
- Integer Programming with a Fixed Number of Variables
- COMPLEXITY OF SHORT GENERATING FUNCTIONS
- Parametric Integer Programming in Fixed Dimension
- Complexity of Subcases of Presburger Arithmetic
- Integer Programming and Algorithmic Geometry of Numbers
- The Computational Complexity of Simultaneous Diophantine Approximation Problems
- Universal diophantine equation
- Short rational generating functions for lattice point problems
- An FPTAS for Minimizing Indefinite Quadratic Forms over Integers in Polyhedra
- Complexity of short Presburger arithmetic
- The computational complexity of integer programming with alternations
- Computational Complexity
- Presburger Arithmetic, Rational Generating Functions, and Quasi-Polynomials
- Integer quadratic programming in the plane
- Integer Polynomial Optimization in Fixed Dimension
- Presburger arithmetic with bounded quantifier alternation
- Algorithms - ESA 2003
- Geometry of continued fractions
This page was built for publication: Short Presburger Arithmetic Is Hard
