1
$\begingroup$
  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$.)
Improve this question
$\endgroup$
7
  • 5
    $\begingroup$ The existence of integer solutions is not computable (MRDP theorem). Whether the existence of rational solutions is computable is a notorious open problem. $\endgroup$
    – Emil Jeřábek
    Nov 3, 2017 at 8:48
  • 2
    $\begingroup$ 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$. $\endgroup$
    – Bruno
    Nov 3, 2017 at 12:37
  • $\begingroup$ @EmilJeřábek it is about the rational solution , not integer solution. $\endgroup$
    – XL _At_Here_There
    Nov 4, 2017 at 0:45
  • $\begingroup$ @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? $\endgroup$
    – XL _At_Here_There
    Nov 4, 2017 at 2:08
  • $\begingroup$ Please ask only one question per post. $\endgroup$
    – D.W.
    Nov 5, 2017 at 17:24

1 Answer 1

Reset to default
2
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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}$ $\endgroup$
    – XL _At_Here_There
    Nov 22, 2017 at 0:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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