Timeline for Complexity of polynomial inequalities
Current License: CC BY-SA 4.0
2 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 13, 2021 at 10:37 | comment | added | Emil Jeřábek | This computational problem is known as the existential theory of the reals. It sits somewhere between NP and PSPACE, but not much more is known; it’s important enough that it’s been given a complexity class of its own ($\exists\mathbb R$). (The official definition as in the Wikipedia article allows the arbitrary existential sentences, but this easily reduces to the case of satisfiability of a single polynomial equation by introduction of a few extension variables.) | |
| Jan 13, 2021 at 10:30 | history | asked | Arnold Neumaier | CC BY-SA 4.0 |