<ol>
<li><p>As already pointed out by Emil Jeřábek in the comments, this is Hilbert's Tenth Problem over the rationals, whose computability is a notorious open question.</p></li>
<li><p>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</p></li>
</ol>

<blockquote>
  <p>Boolean solution iff integer solution iff rational solution w/ odd denominators</p>
</blockquote>

<p>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.</p>

<p>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).</p>

CC BY-SA 3.0
2017-11-22T00:55:42.033Z
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}$
XL _At_Here_There
CC BY-SA 3.0
2017-11-21T15:37:13.000Z
2017-11-21T15:37:13.000Z
Joshua Grochow
<ol>
<li>What is the complexity of the following problem? (e.g. best-known running time, space, best upper bound in terms of complexity classes, etc.)</li>
</ol>
<blockquote>
<p>Input: A multivariate polynomial <span class="math-container">$f$</span> with coefficients over <span class="math-container">$\mathbb{Z}$</span></p>
<p>Decide: Is there a rational zero of <span class="math-container">$f$</span>?</p>
</blockquote>
<ol start="2">
<li>What about the complexity where <span class="math-container">$f$</span> is the translation of a Boolean formula under the standard translation? (viz. <span class="math-container">$t(x) = x$</span>, <span class="math-container">$t(f \vee g) =  1-(1-t(f))(1-t(g))$</span> and <span class="math-container">$t(f \wedge g) = t(f) t(g)$</span>; thus, a <span class="math-container">$\{0,1\}$</span> assignment satisfies <span class="math-container">$f$</span> iff it satisfies the polynomial equation <span class="math-container">$t(f)=1$</span>.)</li>
</ol>

CC BY-SA 3.0
2017-11-03T08:48:43.393Z
The existence of integer solutions is not computable (MRDP theorem). Whether the existence of rational solutions is computable is a notorious open problem.
Emil Jeřábek
CC BY-SA 3.0
2017-11-03T12:37:11.227Z
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$.
Bruno
CC BY-SA 3.0
2017-11-04T00:45:29.887Z
@EmilJeřábek it is about the rational solution , not integer solution.
XL _At_Here_There
CC BY-SA 3.0
2017-11-04T02:08:01.733Z
@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?
XL _At_Here_There
CC BY-SA 3.0
2017-11-05T17:24:02.933Z
Please ask only one question per post.
D.W.
CC BY-SA 3.0
2017-11-20T00:13:16.343Z
@XL_at_China: Do you want to know about the complexity of finding rational solutions of integer polynomials *in general*, or *only for polynomials coming from Boolean equations* (as in your previous comment)?
Joshua Grochow
CC BY-SA 3.0
2017-11-20T06:07:19.233Z
@JoshuaGrochow, rational solutions for polynomials coming from Boolean equations (as in your previous comment) are okay.
XL _At_Here_There
<complexity-classes><algebraic-complexity>
What is the computational complexity of solutions over $\mathbb{Q}$ of polynomial equation with coeffiecents over $\mathbb{Z}$
XL _At_Here_There
# What is the computational complexity of solutions over $\mathbb{Q}$ of polynomial equation with coeffiecents over $\mathbb{Z}$

(Asked by: username_0 on 2017-11-03)

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$?

2. 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$.)

**Tags:** complexity-classes, algebraic-complexity
> **Comments:**
> **username_1**: The existence of integer solutions is not computable (MRDP theorem). Whether the existence of rational solutions is computable is a notorious open problem.  
> **username_2**: 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$.  
> **username_0**: @EmilJeřábek it is about the rational solution , not integer solution.  
> **username_0**: @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?  
> **username_3**: Please ask only one question per post.  
> **username_4**: @XL_at_China: Do you want to know about the complexity of finding rational solutions of integer polynomials *in general*, or *only for polynomials coming from Boolean equations* (as in your previous comment)?  
> **username_0**: @JoshuaGrochow, rational solutions for polynomials coming from Boolean equations (as in your previous comment) are okay.  

---

## 1 answers

### Answer by username_4 on 2017-11-21. Score: 2 | Accepted answer

1. As already pointed out by Emil Jeřábek in the comments, this is Hilbert's Tenth Problem over the rationals, whose computability is a notorious open question.
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

> Boolean solution iff integer solution iff rational solution w/ odd denominators

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).

> **Comments:**
> **username_0**: 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}$  

---

