Complexity of short Presburger arithmetic

DOI10.1145/3055399.3055435zbMath1370.68139arXiv1704.00249OpenAlexW2614001090MaRDI QIDQ4978025

Danny Nguyen, Igor Pak

Publication date: 17 August 2017

Published in: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1704.00249

zbMATH Keywords

integer programmingBarvinok's algorithmPresburger arithmeticKannan's partition theorem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Integer programming (90C10) First-order arithmetic and fragments (03F30)

Related Items (6)

Short Presburger Arithmetic Is Hard ⋮ The Computational Complexity of Integer Programming with Alternations ⋮ Enumerating Projections of Integer Points in Unbounded Polyhedra ⋮ Parameterized resiliency problems ⋮ COMPLEXITY OF SHORT GENERATING FUNCTIONS ⋮ Sparse representation of vectors in lattices and semigroups

This page was built for publication: Complexity of short Presburger arithmetic