Parametric Presburger Arithmetic: Complexity of Counting and Quantifier Elimination

Abstract: We consider an expansion of Presburger arithmetic which allows multiplication by

k

parameters

t_{1}, l d o t s, t_{k}

. A formula in this language defines a parametric set

S_{m} a t h b f t s u b s e t e q m a t h b b Z^{d}

as

m a t h b f t

varies in

m a t h b b Z^{k}

, and we examine the counting function

| S_{m} a t h b f t |

as a function of

m a t h b f 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 extbf{P}

e q

extbf{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_{m} a t h b f t s u b s e t e q m a t h b b Z^{d}

with arbitrarily many parameters, defined in a similar language without the ordering relation, we show that

| S_{m} a t h b f t |

is always polynomial-time computable in the size of

m a t h b f t

, and in fact can be represented using the gcd and similar functions.

This page was built for publication: Parametric Presburger Arithmetic: Complexity of Counting and Quantifier Elimination