<p>The decision version of this problem is obviously in <span class="math-container">$\mathsf{NP}$</span>, and Manders &amp; Adleman showed that a specific case is NP-complete. Namely, even deciding whether there exists an integer <span class="math-container">$x \in [0, \gamma]$</span> such that <span class="math-container">$x^2 \cong \alpha \mod \beta$</span> (the input here is the triple <span class="math-container">$(\alpha,\beta,\gamma)$</span>) 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 <span class="math-container">$\mathsf{\# P}$</span>-complete as well.</p>

CC BY-SA 4.0
2018-10-26T14:05:16.243Z
I assume counting mod $2$ is $\oplus P$ complete as well?
Turbo
CC BY-SA 4.0
2018-10-26T15:29:55.963Z
Assuming I'm right about the parsimony, then yes, of course.
Joshua Grochow
CC BY-SA 4.0
2018-10-30T17:17:47.027Z
The reference is https://doi.org/10.1016/0022-0000(78)90044-2
Peter Taylor
CC BY-SA 4.0
2018-10-26T10:58:50.470Z
2018-10-26T10:58:50.470Z
Joshua Grochow
<p>Deciding integer roots of multivariate polyomials is undecidable. However what is known about counting integer roots of multivariate polynomials  in <span class="math-container">$\mathbb Z[x_1,\dots,x_m]$</span> with both <span class="math-container">$m$</span> and total degree fixed and we only look at integer roots in a bounded polyhedron?</p>

CC BY-SA 4.0
2018-10-25T20:46:33.097Z
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.
Joshua Grochow
CC BY-SA 4.0
2018-10-25T22:21:14.677Z
@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).
Turbo
CC BY-SA 4.0
2018-10-26T00:32:53.003Z
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.
Joshua Grochow
<cc.complexity-theory><nt.number-theory><polynomials><polynomial-time><algebraic-complexity>
Complexity of counting integer roots of multivariate polynomials in a polyhedron?
Turbo
# Complexity of counting integer roots of multivariate polynomials in a polyhedron?

(Asked by: username_0 on 2018-10-25)

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?

**Tags:** cc.complexity-theory, nt.number-theory, polynomials, polynomial-time, algebraic-complexity

> **Comments:**
> **username_1**: 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.  
> **username_0**: @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).  
> **username_1**: 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.  

---

## 1 answers

### Answer by username_1 on 2018-10-26. Score: 5 | Accepted answer

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.

> **Comments:**
> **username_0**: I assume counting mod $2$ is $\oplus P$ complete as well?  
> **username_1**: Assuming I'm right about the parsimony, then yes, of course.  
> **username_2**: The reference is https://doi.org/10.1016/0022-0000(78)90044-2  

---

