7 citations · 22 across the 10 of their papers we have counts for
4 papers · 1 filter
Short Presburger arithmetic is hard
Danny Nguyen, Igor Pak
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, ine…
Complexity of short Presburger arithmetic
Danny Nguyen, Igor Pak
We study complexity of short sentences in Presburger arithmetic (Short-PA). Here by "short" we mean sentences with a bounded number of variables, quantifiers, inequalities and Bool…
The computational complexity of integer programming with alternations
Danny Nguyen, Igor Pak
We prove that integer programming with three quantifier alternations is -complete, even for a fixed number of variables. This complements earlier results by Lenstra and Kannan,…
Complexity of short generating functions
Danny Nguyen, Igor Pak
We give complexity analysis of the class of short generating functions (GF). Assuming , we show that this class is not closed under taking many intersect…