2
$\begingroup$

Let's have a multi-variable high degree polynomial $f(x_1, x_2, \dots, x_n)$. I am looking for efficient way to figure out if there are any roots in real numbers for:

$0 \le x_1 \le 1\\ 0 \le x_2 \le 1\\ \dots\\ 0 \le x_n \le 1$

Can you give some hints, theorems or algorithms for performing such tasks. And I don't need to find roots exactly. I just need to know if there are roots or not.

1 Answers 1

3

It is a famous theorem of Tarski that the first-order theory of the real numbers is decidable. The decision procedure is a quantifier-elimination process that depends on a general root isolation procedure for multivariate polynomials over the reals. There is a nice account online of a simple decision procedure due to Hormander and others. There are implementations of such decision procedures in some computer algebra systems (Mathematica, SAGE) and in some more specialised automated theorem provers (QEPCAD, RAHD). RAHD is specially targeted at problems with many variables.

However, even for the special case you are concerned with, the algorithmic complexity is high. See "Algorithms in Real Algebraic Geometry" by Basu et al. for more information.