Parametric Presburger arithmetic: complexity of counting and quantifier elimination. Issue 2 (2nd September 2019) - Bogart, Tristram; Goodrick, John; Nguyen, Danny; Woods, Kevin
Abstract: 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 oft . 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 oft, and in fact can be represented using the gcd and similar functions.