It can be easily seen that solving systems of polynomial (i.e. not necessarily linear) equations is NP-Hard via reduction from SAT. Furthermore, because the existential theory of the reals is decidable in PSPACE, solving systems of polynomial equations is as well. What else is known about the complexity of this problem? For example, I have been unable to determine if it is known to be $\exists R$-Complete, or PSPACE-Complete.

  • 1
    $\begingroup$ I'm pretty sure it's famously open. The upper bound is PSPACE, and the lower is NP-hardness. But I'm not confident enough about this to put it up as an answer. I will if I find a good reference. $\endgroup$
    – Shaull
    Commented Mar 26, 2018 at 20:10

1 Answer 1


Solving systems of polynomial equations over the reals is $\exists \mathbb R$-complete by definition, and it is a major open problem whether this complexity class equals PSPACE. See this.


Your Answer

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

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