# Existential theory of the reals

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_k \, F(X_1,\dots, X_k), \,$

where F(X1, ..., Xk) is a quantifier-free formula in the language of ordered fields with coefficients in a real closed field.[1]

The decision problem for the existential theory of the reals is the problem of finding an algorithm that decides, for each such formula, whether it is true or false. This decision problem is NP-hard and lies in PSPACE. Thus, it has 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]

## Complete problems

Several problems in computational complexity and geometric graph theory may be classified as complete for the existential theory of the reals. These include:

• recognition of intersection graphs of line segments in the plane (that is, given an undirected graph, determining whether there is a set of line segments that has an isomorphic intersection graph);[2][3]
• recognition of unit disk graphs (again, given only the graph itself as input);[4]
• recognition of unit distance graphs, and testing whether the dimension or Euclidean dimension of a graph is at most a given value.[5]
• recognition of intersection graphs of convex sets in the plane;[2]
• stretchability of pseudolines (that is, given a family of curves in the plane, determining whether they are homeomorphic to a line arrangement);[2][6][7]
• determining the rectilinear crossing number of a graph (the minimum number of pairs of edges that cross in any drawing with edges drawn as straight line segments in the plane);[2][8]
• the algorithmic Steinitz problem (given a lattice, determine whether it is the face lattice of a convex polytope);[9]
• testing whether a given graph can be drawn in the plane with straight line edges and with a given set of edge pairs as its crossings;[10] and
• testing whether a 4-regular graph whose edges are colored with four colors has a drawing with edges as straight line segments of four slopes, with the slopes representing the colors in the coloring.[11]

Based on this, the complexity class $\exists \mathbb{R}$ has been defined as the set of problems having a polynomial-time many-one reduction to the existential theory of the reals.[2]

## References

1. ^ a b Basu, Saugata; Pollack, Richard; Roy, Marie-Françoise (2006), "Existential theory of the reals", Algorithms in Real Algebraic Geometry, Algorithms and Computation in Mathematics 10 (2nd ed.), Springer-Verlag, pp. 505–532, doi:10.1007/3-540-33099-2_14, ISBN 978-3-540-33098-1.
2. Schaefer, Marcus (2010), "Complexity of some geometric and topological problems", Graph Drawing, 17th International Symposium, GS 2009, Chicago, IL, USA, September 2009, Revised Papers, Lecture Notes in Computer Science 5849, Springer-Verlag, pp. 334–344, doi:10.1007/978-3-642-11805-0_32.
3. ^ Kratochvíl, Jan; Matoušek, Jiří (1994), "Intersection graphs of segments", Journal of Combinatorial Theory, Series B 62 (2): 289–315, doi:10.1006/jctb.1994.1071, MR 1305055.
4. ^ Kang, Ross J.; Müller, Tobias (2011), "Sphere and dot product representations of graphs", Proceedings of the Twenty-Seventh Annual Symposium on Computational Geometry (SCG'11), June 13–15, 2011, Paris, France, pp. 308–314.
5. ^ Schaefer, Marcus (2013), "Realizability of graphs and linkages", in Pach, János, Thirty Essays on Geometric Graph Theory, Springer, pp. 461–482, doi:10.1007/978-1-4614-0110-0_24.
6. ^ Mnëv, N. E. (1988), "The universality theorems on the classification problem of configuration varieties and convex polytopes varieties", Topology and geometry—Rohlin Seminar, Lecture Notes in Math. 1346, Berlin: Springer, pp. 527–543, doi:10.1007/BFb0082792, MR 970093.
7. ^ Shor, Peter W. (1991), "Stretchability of pseudolines is NP-hard", Applied Geometry and Discrete Mathematics, DIMACS Ser. Discrete Math. Theoret. Comput. Sci. 4, Providence, RI: American Mathematical Society, pp. 531–554, MR 1116375.
8. ^ Bienstock, Daniel (1991), "Some provably hard crossing number problems", Discrete and Computational Geometry 6 (5): 443–459, doi:10.1007/BF02574701, MR 1115102.
9. ^ Björner, Anders; Las Vergnas, Michel; Sturmfels, Bernd; White, Neil; Ziegler, Günter M. (1993), Oriented Matroids, Encyclopedia of Mathematics and its Applications 46, Cambridge: Cambridge University Press, Corollary 9.5.10, p. 407, ISBN 0-521-41836-4, MR 1226888.
10. ^ Kynčl, Jan (2011), "Simple realizability of complete abstract topological graphs in P", Discrete and Computational Geometry 45 (3): 383–399, doi:10.1007/s00454-010-9320-x, MR 2770542.
11. ^ Richter, David A. (2011), "How to draw a Tait-colorable graph", in Brandes, Ulrik; Cornelsen, Sabine, Proc. 18th International Symposium on Graph Drawing (GD 2010), Lecture Notes in Computer Science 6502, Springer-Verlag, pp. 353–364, doi:10.1007/978-3-642-18469-7_32.