# What is the computational complexity of solutions over $\mathbb{Q}$ of polynomial equation with coeffiecents over $\mathbb{Z}$

1. What is the complexity of the following problem? (e.g. best-known running time, space, best upper bound in terms of complexity classes, etc.)

Input: A multivariate polynomial $$f$$ with coefficients over $$\mathbb{Z}$$

Decide: Is there a rational zero of $$f$$?

1. What about the complexity where $$f$$ is the translation of a Boolean formula under the standard translation? (viz. $$t(x) = x$$, $$t(f \vee g) = 1-(1-t(f))(1-t(g))$$ and $$t(f \wedge g) = t(f) t(g)$$; thus, a $$\{0,1\}$$ assignment satisfies $$f$$ iff it satisfies the polynomial equation $$t(f)=1$$.)
• The existence of integer solutions is not computable (MRDP theorem). Whether the existence of rational solutions is computable is a notorious open problem. Nov 3 '17 at 8:48
• Emil's comment is of course for the multivariate case. For univariate polynomials, computing (integer or rational) roots is polynomial. In the multivariate case, the minimal number of variables to get indecidability is not known, but is known to be at most $11$ (I've not heard of better bounds). No idea about the complexity of finding integer (or rational) roots for fixed number $n$ of variables, for any $n$ between $2$ and $10$. Nov 3 '17 at 12:37
• @EmilJeřábek it is about the rational solution , not integer solution. Nov 4 '17 at 0:45
• @EmilJeřábek By transformations like $x_1\bigvee x_2$ to $x_1+x_2-x_1x_2$ and other rules, we can get polynomial fro every boolean formula. Now what is the computational complexity to compute the rational solution over $\mathbb{Z}$ to the polynomial? Nov 4 '17 at 2:08
– D.W.
Nov 5 '17 at 17:24

2. In this case, note that the Boolean formula $f$ is satisfiable iff $t(f)$ has an integer zero: a satisfying assignment, when treated as 0s and 1s, gives an integer zero, and conversely, given an integer zero $\vec{\alpha}$, taking it mod 2 gives a satisfying Boolean assignment (this follows from the form of the translation $t(\bullet)$). Now, given a rational solution to $t(f)=0$, if all of the denominators involved are odd, then we may still take it mod 2 to get a Boolean solution, so we have
Therefore, deciding the existence of integer roots or of rational roots with odd denominators for polynomials of the form $t(f)$ is $\mathsf{NP}$-complete.
This leaves us with the question of how hard it is to decide existence of a rational root of $t(f)$ in general (that is, without restriction on the denominators). I do not know anything more about this question than about Hilbert's Tenth Problem over $\mathbb{Q}$ (addressed in Q1).
• Yes, this is why I ask the question, I hope we may have some new intuition about the NPC problem or Hilbert Tenth Problem over $\mathbb{Q}$ Nov 22 '17 at 0:55