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?
$\begingroup$
$\endgroup$
3
-
1$\begingroup$ 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. $\endgroup$– Joshua GrochowCommented Oct 25, 2018 at 20:46
-
$\begingroup$ @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). $\endgroup$– TurboCommented Oct 25, 2018 at 22:21
-
1$\begingroup$ 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. $\endgroup$– Joshua GrochowCommented Oct 26, 2018 at 0:32
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
3
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.
answered Oct 26, 2018 at 10:58
-
$\begingroup$ I assume counting mod $2$ is $\oplus P$ complete as well? $\endgroup$– TurboCommented Oct 26, 2018 at 14:05
-
$\begingroup$ Assuming I'm right about the parsimony, then yes, of course. $\endgroup$ Commented Oct 26, 2018 at 15:29
-
$\begingroup$ The reference is doi.org/10.1016/0022-0000(78)90044-2 $\endgroup$ Commented Oct 30, 2018 at 17:17