Name
Abstract | ||
|---|---|---|
We consider an expansion of Presburger arithmetic which allows multiplication by k parameters t1, horizontal ellipsis ,tk. A formula in this language defines a parametric set St subset of Zd as t varies in Zk, 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 not equal 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 subset of Zd 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. |
Year | DOI | Venue |
|---|---|---|
2018 | 10.1002/malq.201800068 | MATHEMATICAL LOGIC QUARTERLY |
Field | DocType | Volume |
Quantifier elimination,Discrete mathematics,Arithmetic,Presburger arithmetic,Parametric statistics,Mathematics | Journal | 65 |
Issue | ISSN | Citations |
2 | 0942-5616 | 0 |
PageRank | References | Authors |
0.34 | 4 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Tristram Bogart | 1 | 13 | 3.54 |
| John Goodrick | 2 | 26 | 7.57 |
| Danny Nguyen | 3 | 14 | 4.20 |
| Kevin M. Woods | 4 | 25 | 6.04 |