Parametric Presburger arithmetic: complexity of counting and quantifier elimination. Issue 2 (2nd September 2019)

• Record Type: Journal Article
• Authors: Bogart, Tristram; Goodrick, John; Nguyen, Danny; Woods, Kevin
• Is Part Of: Mathematical logic quarterly. Volume 65:Issue 2(2019)
• Page Start: 237
• Page End: 250
• Publication Date: 2019-09-02
• Subjects: Mathematics -- Periodicals; Logic, Symbolic and mathematical -- Periodicals; 511.3
• DOI: 10.1002/malq.201800068
• Languages: English
• ISSNs: 0942-5616

Abstract

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.