|
Parametric Presburger arithmetic concerns families of sets defined using quantifiers and Boolean combinations of formulas of the form a(t)·x ≤ b(t), where a(t) ∈ Z[t] d , b(t) ∈ Z[t]. In the quantifier-free these formulas represent sets of integer points in families of (unions of) polyhedra with polynomially varying facet inequalities. With quantifiers, they may represent more general sets such as polynomially varying families of numerical semigroups. The Ehrhart theorem, its many generalizations, and more recent results of Chen, Li, and Sam; Calegari and Walker; Roune and Woods; and Shen concern specific families in parametric Presburger arithmetic that exhibit quasi-polynomial behavior. For example, |S_t| might be a quasi-polynomial function of t or an element x(t) ∈ S_t might be specifiable as a function with quasi-polynomial coordinates for sufficiently large t. Woods conjectured that all parametric Presburger sets exhibit this quasi-polynomial behavior. With Goodrick and Woods, we proved this conjecture, using various tools from logic and combinatorics. Analogously, k-parametric Presburger arithmetic concerns families of sets defined in the same way but with Z[t] replaced by Z[t_1, ..., t_k]. Building on recent work of Nguyen and Pak, we prove with Goodrick, Nguyen and Woods the following result in stark contrast to the 1-parameter case: if P != NP, then there are 2-parametric Presburger families whose counting function |S(t_1,t_2)| cannot even be evaluated in polynomial time.
|
