Existential theory of the reals information

In mathematical logic, computational complexity theory, and computer science, the existential theory of the reals is the set of all true sentences of the form

\exists X_{1}\cdots \exists X_{n}\,F(X_{1},\dots ,X_{n}),

where the variables

X_{i}

are interpreted as having real number values, and where

F(X_{1},\dots X_{n})

is a quantifier-free formula involving equalities and inequalities of real polynomials. A sentence of this form is true if it is possible to find values for all of the variables that, when substituted into formula

F

, make it become true.^[1]

The decision problem for the existential theory of the reals is the problem of finding an algorithm that decides, for each such sentence, whether it is true or false. Equivalently, it is the problem of testing whether a given semialgebraic set is non-empty.^[1] This decision problem is NP-hard and lies in PSPACE,^[2] giving it significantly lower complexity than Alfred Tarski's quantifier elimination procedure for deciding statements in the first-order theory of the reals without the restriction to existential quantifiers.^[1] However, in practice, general methods for the first-order theory remain the preferred choice for solving these problems.^[3]

The complexity class $\exists \mathbb {R}$ has been defined to describe the class of computational problems that may be translated into equivalent sentences of this form. In structural complexity theory, it lies between NP and PSPACE. Many natural problems in geometric graph theory, especially problems of recognizing geometric intersection graphs and straightening the edges of graph drawings with crossings, belong to $\exists \mathbb {R}$ , and are complete for this class. Here, completeness means that there exists a translation in the reverse direction, from an arbitrary sentence over the reals into an equivalent instance of the given problem.^[4]

^ ^a ^b ^c Basu, Saugata; Pollack, Richard; Roy, Marie-Françoise (2006), "Existential theory of the reals", Algorithms in Real Algebraic Geometry, Algorithms and Computation in Mathematics, vol. 10 (2nd ed.), Springer-Verlag, pp. 505–532, doi:10.1007/3-540-33099-2_14, ISBN 978-3-540-33098-1.
^ Canny, John (1988), "Some algebraic and geometric computations in PSPACE", Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing (STOC '88, Chicago, Illinois, USA), New York, NY, USA: ACM, pp. 460–467, doi:10.1145/62212.62257, ISBN 0-89791-264-0, S2CID 14535463
^ Cite error: The named reference pj09 was invoked but never defined (see the help page).
^ Cite error: The named reference s09 was invoked but never defined (see the help page).

[bpr06-1] Basu, Saugata; Pollack, Richard; Roy, Marie-Françoise (2006), "Existential theory of the reals", Algorithms in Real Algebraic Geometry, Algorithms and Computation in Mathematics, vol. 10 (2nd ed.), Springer-Verlag, pp. 505–532, doi:10.1007/3-540-33099-2_14, ISBN 978-3-540-33098-1.

[canny-2] Canny, John (1988), "Some algebraic and geometric computations in PSPACE", Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing (STOC '88, Chicago, Illinois, USA), New York, NY, USA: ACM, pp. 460–467, doi:10.1145/62212.62257, ISBN 0-89791-264-0, S2CID 14535463

[pj09-3] Cite error: The named reference pj09 was invoked but never defined (see the help page).

[s09-4] Cite error: The named reference s09 was invoked but never defined (see the help page).

Existential theory of the reals information

and 22 Related for: Existential theory of the reals information

Existential theory of the reals

Real closed field

Semialgebraic set

Existential therapy

Intersection graph

John Canny

James Renegar

Unit distance graph

Existential quantification

Humanistic psychology

Unit disk graph

Kissing number

Existentialism

Existential nihilism

Packing problems

Polyhedral combinatorics

Existential risk from artificial general intelligence

Death anxiety

Syllogism

Edge coloring

Conspiracy theory

Global catastrophic risk