5
$\begingroup$

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?

$\endgroup$
  • 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 Grochow Oct 25 '18 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$ – Brout Oct 25 '18 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 Grochow Oct 26 '18 at 0:32
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I assume counting mod $2$ is $\oplus P$ complete as well? $\endgroup$ – Brout Oct 26 '18 at 14:05
  • $\begingroup$ Assuming I'm right about the parsimony, then yes, of course. $\endgroup$ – Joshua Grochow Oct 26 '18 at 15:29
  • $\begingroup$ The reference is doi.org/10.1016/0022-0000(78)90044-2 $\endgroup$ – Peter Taylor Oct 30 '18 at 17:17

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.