Parametric Presburger Arithmetic: Complexity of Counting and Quantifier Elimination
share
We consider an expansion of Presburger arithmetic which allows multiplication by k parameters t_1,...,t_k. A formula in this language defines a parametric set S_t⊆Z^d as t varies in Z^k, and we examine the counting function |S_t| as a function of t. For a single parameter, it is known that |S_t| 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 S_t_1,t_2 such that |S_t_1, t_2| is not even polynomial-time computable on input (t_1,t_2). In contrast, for parametric sets S_t⊆Z^d with arbitrarily many parameters, defined in a similar language without the ordering relation, we show that |S_t| is always polynomial-time computable in the size of t, and in fact can be represented using the gcd and similar functions.
READ FULL TEXT