5
$\begingroup$

Some definitions of the existential theory of the reals (ETR) allow a real closed field and some definitions allow only rational numbers as coefficients of polynomials. Which one is correct? Will the answer to the question have an effect on the PSPACE proof by J. Canny? For example, ETR is not in PSPACE, if numbers in real closed field are allowed as coefficients?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
4
$\begingroup$

In order for this to be a computational problem in the first place, you have to fix a representation of the coefficients by finite strings (which in particular implies that the field is countable). The answer will in general depend on the representation.

For the most obvious case, if the coefficients are taken from the field of real algebraic numbers, and are represented in a common way (minimal polynomial + an isolating interval or a BKR sign condition), then the problem is equivalent to the one with rational coefficients, because we can just plug the definitions of the coefficients into the formula.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thanks for your answer. Is it correct that we then have to introduce one equation and one new fresh variable for each coefficient, if we choose, for example, the minimal polynomial representation for the coefficients? Won't it blow up the complexity? $\endgroup$
    – dschaehi
    Commented Mar 8, 2013 at 15:27
  • $\begingroup$ For each coefficient, you introduce one variable, an equation stating the variable is a root of the respective polynomial, and something to uniquely pick up the particular root: for example, if the coefficient is specified as the unique root of $f(x)$ in the interval $[a,b]$, you would include the inequalities $x-a\ge0$ and $b-x\ge0$ (which can be combined to $(x-a)(b-x)\ge0$). This is a polynomial-time reduction, the description of the new system has length polynomial in the length of the original input (in effect, it is the same input organized in a different way). ... $\endgroup$
    – Emil Jeřábek
    Commented Mar 8, 2013 at 17:06
  • $\begingroup$ ... In particular, a PSPACE-algorithm for the problem with rational coefficients will give a PSPACE-algorithm for the more general problem. I have no practical experience with such problems, so I have no idea how much would it affect practical performance of the algorithm, or whether a different reduction might be more suitable, but for theoretical purposes, this preserves the computational complexity of the problem. $\endgroup$
    – Emil Jeřábek
    Commented Mar 8, 2013 at 17:11
  • $\begingroup$ in practice, exact symbolic algorithms for ETR are quite slow; in particular, the running time is exponential in the number of variables, with a largish constant. Algorithms based on sums of squares relaxations are faster, although the computations they perform are only approximate, implying all sorts of theoretical nastiness. $\endgroup$
    – Dima Pasechnik
    Commented Mar 9, 2013 at 7:27

You must log in to answer this question.