# Complexity of counting integer roots of multivariate polynomials in a polyhedron?

Deciding integer roots of multivariate polyomials is undecidable. However what is known about counting integer roots of multivariate polynomials in $$\mathbb Z[x_1,\dots,x_m]$$ with both $$m$$ and total degree fixed and we only look at integer roots in a bounded polyhedron?

• Seeing as the unbounded problem remains uncomputable even with 9 variables and bounded degree, I'd be very surprised if the counting problem inside a bounded polytope weren't #P-complete. Certainly #P is an upper bound. Oct 25 '18 at 20:46
• @JoshuaGrochow I think you may be right and I am not posing properly ($\#\{(x,y)\in\mathbb Z^2\cap\mathcal P:xy-N=0\}$ is conjecturally hard).
– Mr.
Oct 25 '18 at 22:21
• With $xy-N$ you don't even need the polytope, since it is easy to derive from the equation bounds on any possible solutions. Also, as I'm sure you realize, it's only as hard as factoring, whereas I believe the general problem you posed is NP-complete. Oct 26 '18 at 0:32

The decision version of this problem is obviously in $$\mathsf{NP}$$, and Manders & Adleman showed that a specific case is NP-complete. Namely, even deciding whether there exists an integer $$x \in [0, \gamma]$$ such that $$x^2 \cong \alpha \mod \beta$$ (the input here is the triple $$(\alpha,\beta,\gamma)$$) is NP-complete, which is only one variable and degree 2. I haven't checked the details in a while, but I'm pretty sure their reduction is parsimonious; if so, the counting version you ask about will be $$\mathsf{\# P}$$-complete as well.
• I assume counting mod $2$ is $\oplus P$ complete as well?