2018/02/03 by Bogart, Tristram, Goodrick, John, Nguyen, Danny +1 · 1 citation
#03C10 #52B20 #68Q17 #Combinatorics (math.CO) #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics #Logic (math.LO)
paper · doi:10.48550/arxiv.1802.00974
We consider an expansion of Presburger arithmetic which allows multiplication by k parameters t1,…,tk. A formula in this language defines a parametric set St ⊆ ℤd as t varies in ℤk, and we examine the counting function |St| as a function of t. For a single parameter, it is known that |St| can be expressed as an eventual quasi-polynomial (there is a period m such that, for sufficiently large t, the function is polynomial on each of the residue classes mod m). We show that such a nice expression is impossible with 2 or more parameters. Indeed (assuming P ≠ NP) we construct a parametric set St1,t2 such that |St1, t2| is not even polynomial-time computable on input (t1,t2). In contrast, for parametric sets St ⊆ ℤd with arbitrarily many parameters, defined in a similar language without the ordering relation, we show that |St| is always polynomial-time computable in the size of t, and in fact can be represented using the gcd and similar functions.