most recent 30 from http://mathoverflow.net 2013-05-21T06:04:53Z http://mathoverflow.net/feeds/question/83514 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/83514/algorithm-for-checking-existance-of-real-roots-for-polynomials-in-more-than-one-v ostap bender 2011-12-15T12:45:43Z 2011-12-15T13:47:53Z

<p>Is there a way to determine exactly (without the use of approximation methods) whether $p\in \mathbb{R}[x_1,\dots,x_n]$ has real-valued solutions. </p> <p>Algorithms based on Sturm's theorem seem to be applicable to univariate polynomials only. </p>

http://mathoverflow.net/questions/83514/algorithm-for-checking-existance-of-real-roots-for-polynomials-in-more-than-one-v/83515#83515 Boris Novikov 2011-12-15T13:07:28Z 2011-12-15T13:07:28Z

<p>This problem is solved in so-called Semi-algebraic Geometry. Here are some books:</p> <p>Basu S. Algorithms in Semi-algebraic Geometry</p> <p>Basu S., Pollack R., Roy M.-F. Algorithms in Real Algebraic Geometry</p> <p>Bochnak J., Coste M., Roy M-F. Real algebraic geometry</p> <p>Coste M. An introduction to semialgebraic geometry</p>

http://mathoverflow.net/questions/83514/algorithm-for-checking-existance-of-real-roots-for-polynomials-in-more-than-one-v/83521#83521 Joel David Hamkins 2011-12-15T13:40:33Z 2011-12-15T13:47:53Z

<p>Tarski's theorem on the <a href="http://en.wikipedia.org/wiki/Real-closed_field" rel="nofollow">decidability of the theory of real-closed fields</a> provides a general algorithm that decides any question expressible in the first order language of real-closed fields. His algorithm can therefore determine, for any statement, whether it is true in the structure $\langle\mathbb{R},+,\cdot,0,1,\lt\rangle$. Thus, not only are the purely existential assertions (solvability of systems of equations) decidable in this context, but also more complex assertions involving iterated quantifiers, which would not seem without this result to be decidable even by approximation. </p> <p>The way Tarski's argument proceeds is by <a href="http://en.wikipedia.org/wiki/Elimination_of_quantifiers" rel="nofollow">elimination of quantifiers</a>: every assertion in this language is equivalent to a quantifier-free assertion. In particular, the existence of a solution to $p(\vec x)=0$ is equivalent by Tarski's reduction to a quantifier-free assertion about the coefficients of the polynomial. That is, the algorithm reduces the question to a mere calculation involving the coefficients. </p> <p>But if you are interested in actually using the algorithm in specific instances, rather than the theoretical question about whether in principal there is such an algorithm, then Tarski's algorithm may not actually be helpful. Although it has been implemented on computers, the algorithm takes something like a tower of exponential time in the size of the input, and evidently it has been proved that every quantifier-elimination algorithm must be at least double-exponential.</p>