Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

1 Answer 1

up vote 3 down vote accepted

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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