$\forall \exists \mathbb {R}$-Completeness and Area-Universality

Abstract

In the study of geometric problems, the complexity class $\exists \mathbb {R}$ plays a crucial role since it exhibits a deep connection between purely geometric problems and real algebra. Sometimes $\exists \mathbb {R}$ is referred to as the “real analogue” to the class NP. While NP is a class of computational problems that deals with existentially quantified boolean variables, $\exists \mathbb {R}$ deals with existentially quantified real variables.

In analogy to $\varPi _2^p$ and $\varSigma _2^p$ in the famous polynomial hierarchy, we study the complexity classes $\forall \exists \mathbb {R}$ and $\exists \forall \mathbb {R}$ with real variables. Our main interest is focused on the Area Universality problem, where we are given a plane graph G, and ask if for each assignment of areas to the inner faces of G there is an area-realizing straight-line drawing of G. We conjecture that the problem Area Universality is $\forall \exists \mathbb {R}$-complete and support this conjecture by a series of partial results, where we prove $\exists \mathbb {R}$- and $\forall \exists \mathbb {R}$-completeness of variants of Area Universality. To do so, we also introduce first tools to study $\forall \exists \mathbb {R}$. Finally, we present geometric problems as candidates for $\forall \exists \mathbb {R}$-complete problems. These problems have connections to the concepts of imprecision, robustness, and extendability.

A video presenting this paper is available at https://youtu.be/OQkACiNS66o. Proofs omitted due to space constraints can be found in the full version of the manuscript [6]

T. Miltzow—Partially supported by the ERC grant PARAMTIGHT: “Parameterized complexity and the search for tight complexity results”, no. 280152.

1 Introduction

In this paper we investigate problems related to face areas in straight-line drawings of planar graphs. We consider two crossing-free drawings of a planar graph to be equivalent if they have the same outer face and rotation system, i.e., for each vertex the cyclic ordering of the incident edges coincides. Recall that a plane graph is a planar graph together with a crossing-free drawing, and the faces of a plane graph are determined by its rotation system. Let G be a plane graph and let F be the set of inner faces of G. A face area assignment is a function $\mathcal {A} :F \rightarrow \mathbb {R}^+_0$. We say that $G'$ is an $\mathcal {A}$ -realizing drawing, if $G'$ is an equivalent straight-line drawing of G in which the area of each $f \in F$ is exactly $\mathcal {A} (f)$. If $\mathcal {A}$ has an area-realizing drawing, we say that $\mathcal {A}$ is realizable. A plane graph G is area-universal if every face area assignment is realizable. Since we only consider crossing-free straight-line drawings, we simply call them drawings from now on.

Since area-universality seems to be a strong property, it is somewhat surprising that many graphs indeed are easily seen to be area-universal. It is straightforward to observe that stacked triangulations, also known as planar 3-trees or Apollonian networks, are area-universal. A stacked triangulation T is defined recursively by subdividing a triangle t of a stacked triangulation $T'$ into three smaller triangles. An area assignment of T can be realized by first realizing $T'$ so that t has the total area of the three smaller triangles, and then subdividing t accordingly. Moreover, it is easy to see that if a graph is area-universal, then each of its subgraphs is also area-universal. These two observations together imply that partial planar 3-trees are area-universal [3]. In 1992, Thomassen [17] proved that plane cubic graphs are area-universal. More recently, Kleist [9] showed that all 1-subdivisions of plane graphs are area-universal. In other words, every area assignment of every plane graph could be realized if we allowed each edge to have at most one bend instead of only allowing straight-line drawings.

For a long time, the only graph known not to be area-universal was the octahedron graph (or graphs containing the octahedron), which was proven by Ringel [15] in 1990. Kleist [9] introduced the first non-trivial infinite family of non-area-universal graphs. In particular, she showed that all Eulerian triangulations and the icosahedron graph are not area-universal. This implies that high connectivity of a graph does not imply area-universality. Moreover, area-universality is not a minor-closed property, as the grid is area-universal [8], but the octahedron graph is not area-universal, although it is a minor of the grid.

In this paper we are interested in the computational problem of deciding if a given plane graph is area-universal; which we denote by Area Universality.

When investigating natural geometric problems, one often discovers that an instance of such a problem can be described by a system of polynomial equations and inequalities $\varPhi$ so that real-valued variable assignments that satisfy $\varPhi$ correspond to solutions of the original geometric problem. Existential Theory of the Reals (ETR) is a computational problem that takes a first-order formula containing only existential quantifiers: $\exists X_1,X_2,\ldots ,X_n :\varPhi$, where $\varPhi$ has symbols 0, 1, $+$, $*$, $=$, <, $\wedge$, $\lnot$, (, ), $X_1$, $\dots ,X_n$ as an input and asks whether it is true or not over the reals. The complexity class $\exists \mathbb {R}$ consists of all problems that are many-one reducible to ETR by a Turing machine in at most a polynomial number of steps. Surprisingly many natural geometric problems appear to be $\exists \mathbb {R}$-complete, i.e., ETR is also reducible to these problems in $\exists \mathbb {R}$ in the above sense. A prominent example is the stretchability of a pseudoline arrangement (see [12, 13, 16]). A pseudoline arrangement in the plane is a set of unbounded Jordan curves where every pair of curves intersects in exactly one crossing point. A pseudoline arrangement is stretchable if there exists an arrangement of straight lines with the same face structure. Stretchability is a computational problem which asks whether a given pseudoline arrangement is stretchable. Here the input is the order type of a pseudoline arrangement, which is a rank 3 chirotope. Since Stretchability is $\exists \mathbb {R}$-complete, there is little hope to find a simple algorithm for Stretchability, since simple algorithms to decide ETR are not known despite tremendous work in real algebraic geometry. The $\exists \mathbb {R}$-completeness of Stretchability reflects the deep algebraic connections between line arrangements and real algebra. For instance, the smallest non-strechable pseudoline arrangement, depicted in Fig. 1, is based on Pappus’s Hexagon Theorem [10], dating back to the 4th century. It considers two different lines with three points each, the points are denoted by A, B, C and X, Y, Z, see Fig. 1. If the lines $\overline{AY} , \overline{BZ}, \overline{CX}$ intersect the lines $\overline{BX}, \overline{CY} , \overline{AZ}$, respectively, then the three points of intersection are collinear. Although the statement is intrinsically geometric, most known proofs are algebraic, see [14].

Fig. 1.

Pappus’s Hexagon Theorem and non-stretchable pseudoline arrangement.

Geometric problems that are $\exists \mathbb {R}$-complete usually ask for the existence of certain objects, satisfying some semialgebraic properties. However, the nature of Area Universality seems to be different. We therefore define the new complexity class $\forall \exists \mathbb {R}$ as the set of all problems that reduce in polynomial time to Universal Existential Theory of the Reals (UETR).

The class $\exists \forall \mathbb {R}$ is defined analogously. Clearly $\exists \mathbb {R}$ is contained in $\forall \exists \mathbb {R}$. It is easy to observe and well-known that NP is contained in $\exists \mathbb {R}$. Highly non-trivial is the containment of $\forall \exists \mathbb {R}$ in PSPACE, which follows from a more general result that deciding first-order formulae over the reals with bounded number of quantifier blocks is in PSPACE (see [2]). For all we know, all these complexity classes could collapse, as we do not know whether NP and PSPACE constitute two different or the same complexity class, see Fig. 2. However, $\exists \mathbb {R}$ $\ne$ $\forall \exists \mathbb {R}$ can be believed with similar confidence as NP $\ne \varPi ^p_2$. In addition, it is known that the algebraic expressibility of $\forall \exists \mathbb {R}$-formulae is larger than $\exists \mathbb {R}$-formulae, see [5].

It is worth mentioning that Blum et al. [4] also introduce a hierarchy of complexity classes analogous to the complexity class NP, but over the reals (this generalizes to other rings). Their canonical model of computation is the so-called Blum-Shub-Smale machine (BSS). The main difference between these approaches is that BSS accepts real numbers as input, while the classes ($\exists \mathbb {R}$, $\forall \exists \mathbb {R}$, $\exists \forall \mathbb {R}$) work with ordinary Turing machines, accepting only strings over finite alphabets.

Fig. 2.

Relation of complexity classes.

Our Results

It is straightforward to show that Area Universality belongs to $\forall \exists \mathbb {R}$:

Proposition 1

Area Universality is in $\forall \exists \mathbb {R}$.

The idea is to use a block of universal quantifiers to describe the face area assignment and the block of existential quantifiers to describe the placement of the vertices of the drawing of G. We believe that a stronger statement holds.

Conjecture 1

Area Universality is $\forall \exists \mathbb {R}$-complete.

While this conjecture, if true, would show that Area Universality is a really difficult problem in an algebraic and combinatorial sense, it would also give the first known natural geometric problem that is complete for $\forall \exists \mathbb {R}$.

As a first step towards proving our conjecture, we consider three variants of Area Universality, each approaching the conjecture from a different direction. In Sect. 2 we introduce restricted variants of ETR and UETR which are still complete and may be useful to show hardness for other problems.

Note that two variants that we consider have the spirit of extending a partial drawing with some extra constraints. This problem was shown recently to be $\exists \mathbb {R}$-complete [11]. This work is the first to show $\exists \mathbb {R}$-hardness for a problem of drawing a planar graph in the plane.

As a starting point we drop the planarity restriction. For a plane graph G with vertex set V, the face hypergraph of G has vertex set V, and its edges correspond to sets of vertices forming the faces (see e.g. [7]). Observe that the face hypergraph of a plane triangulation is 3-uniform, i.e. each hyperedge has 3 vertices. It is clear that Area Universality can be equivalently formulated in the language of face hypergraphs. This relation motivates the following partial assignment (PA) version of the problem.

Theorem 1

Area Universality for Triples PA is $\forall \exists \mathbb {R}$-complete.

For the proof of Theorem 1 we use gadgets similar to the von Staudt constructions used to show the $\exists \mathbb {R}$-hardness of order-types, see [12].

Our second result concerns a variant, where we investigate the complexity of realizing a specific area assignment. Prescribed Area denotes the following problem: Given a plane graph G with an area assignment $\mathcal {A}$, does there exist a crossing-free drawing of G that realizes $\mathcal {A}$? We study a partial extension (PE) version of Prescribed Area, where some vertex positions are fixed and we seek for an area-realizing placement of the remaining vertices.

We show the following hardness result for Prescribed Area PE.

Theorem 2

Prescribed Area PE is $\exists \mathbb {R}$-complete.

The next two results consider the corresponding question for simplicial complexes in three dimensions. Recall that an abstract simplicial complex is a family $\varSigma$ of non-empty finite sets over a ground set $V = \bigcup \varSigma$, which is closed under taking non-empty subsets. We say $\varSigma$ is pure when the inclusion-wise maximal sets of $\varSigma$ all have the same number of elements. We say $\varSigma$ is realizable when there is a simplicial complex $\mathcal {S}$ in $\mathbb {R} ^3$ that has a vertex for each element of V and a simplex corresponding to each set in $\varSigma$.

A crossing-free drawing of $\varSigma$ is a mapping of every $i \in V$ to a point $p_i \in \mathbb {R} ^3$, such that the following holds. For any pair of sets $\sigma _1,\sigma _2 \in \varSigma$ there is a separating hyperplane such that for all $i \in \sigma _1$ and for all $i \in \sigma _2$. A volume assignment for $\varSigma$ is a non-negative-valued function on the collection T of all 4-element sets in $\varSigma$, and a crossing-free drawing of $\varSigma$ realizes a volume assignment $\mathcal {V}: T \rightarrow \mathbb {R}^+_0$ when for each $\tau \in T$, the convex hull of the points $\{p_i : i \in \tau \}$ has volume $\mathcal {V} (\tau )$. The analogous questions are:

Proposition 2

Volume Universality PA is in $\forall \exists \mathbb {R}$.

Note that 3-dimensional simplicial complexes are the analogue of planar triangulations. Indeed, Prescribed Area for triangulations reduces to Prescribed Volume in the following sense:

Proposition 3

There is a polynomial time algorithm that takes as input any plane triangulation G with positive area assignment $\mathcal {A}$ and outputs a simplicial complex $\mathcal {S}$ with volume assignment $\mathcal {V}$ such that $\mathcal A$ is realizable for G if and only if $\mathcal {V}$ is realizable for $\mathcal {S}$.

Moreover, the analogues of $\textsc {Prescribed Area}$ and $\textsc {Area Universality}$ are hard. The two versions read as follows:

Theorem 3

Prescribed Volume is $\exists \mathbb {R}$-complete.

Theorem 4

Volume Universality PA is $\forall \exists \mathbb {R}$-complete.

2 Toolbox: Hard Variants of ETR and UETR

In this section we introduce some restricted variants of ETR and UETR which enable us to show hardness. Recently, Abrahamsen et al. showed that the following problem is also $\exists \mathbb {R}$-complete [1].

In order to define an even more restricted variant of ETRINV, we need one more definition. Consider a formula $\varPhi$ of the form $\varPhi = \varPhi _1 \wedge \varPhi _2 \wedge \ldots \wedge \varPhi _m$, where each $\varPhi _i$ is a quantifier-free formula of the first-order theory of the reals with variables $X_1,X_2,\ldots ,X_n$, which uses arithmetic operators and comparisons ($=,<,\le$) but no logic symbols. The incidence graph of $\varPhi$ is the bipartite graph with vertex set $\{X_1,X_2,\ldots ,X_n\}\,\cup \,\{\varPhi _1,\varPhi _2,\ldots ,\varPhi _m\}$ that has an edge $X_i\varPhi _j$ if and only if the variable $X_i$ appears in the subformula $\varPhi _j$. By Planar-ETRINV we denote the variant of ETRINV where the incidence graph of $\varPhi$ is planar and $\varPhi$ is either unsatisfiable or has a solution with all variables within (0, 5).

Fig. 3.

The crossing gadget.

Theorem 5

Planar-ETRINV is $\exists \mathbb {R}$-complete.

Proof

Let $\left( \exists \; X_1,X_2,\ldots ,X_n \right) :\varPhi$ be an instance of ETRINV and let G be some embedding of $G(\varPhi )$ in $\mathbb {R} ^2$. Suppose that G is not crossing-free and consider a pair of crossing edges. Let X and Y denote the variables corresponding to (one endpoint of) these edges. We introduce three new existential variables $X',Y',Z$ and three constraints: $X + Y = Z;\ X + Y' = Z;\ X' + Y = Z$. Observe that these constraints ensure that $X = X'$ and $Y=Y'$. Moreover, the embedding of G can be modified so that the new incidence graph has strictly fewer crossings (see Fig. 3): the considered crossing is removed and no new crossing is introduced. We repeat this procedure until the incidence graph of the obtained formula is planar. Finally, note that $0< 1 \le Z = X + Y \le 4<5$ whenever $1/2 \le X,Y \le 2$. Note that the number of new variables and constraints is at most $O(|\varPhi |^4)$, since each constraint in ETRINV has at most three variables.    $\square$

Now we introduce a restricted variant of UETR.

Constrained-UETR can be seen as a variant of $\forall \exists \mathbb {R}$ that is simplified in a way analogous to a $\exists \mathbb {R}$-complete variant of ETR called Ineq [12, 16]. Similarly, we will show that Constrained-UETR is $\forall \exists \mathbb {R}$-complete.

Theorem 6

Constrained-UETR is $\forall \exists \mathbb {R}$-complete.

3 Hardness of Area Universality for Triples PA

Here we prove Theorem 1.

Theorem 1

Area Universality for Triples PA is $\forall \exists \mathbb {R}$-complete.

Proof

For the containment, it is easy to express the area of a triangle by a polynomial equation: Denoting the coordinates of a vertex $v_i$ by $(x_i,y_i)$, the signed area $A(v_1,v_2,v_3)$ of a counter-clockwise triangle $v_1v_2v_3$ can be computed by

$$ 2\cdot A(v_1,v_2,v_3) = \det \left( \begin{array}{lll} x_1 &{} x_2 &{} x_{3} \\ y_1 &{} y_2 &{} y_{3} \\ 1 &{} 1 &{} 1 \end{array} \right) =: \text {Det}(v_{1},v_{2},v_{3}). $$

Thus, we take a conjunction of equations of the above form for each triple.

For the hardness, we reduce from $\textsc {Constrained-UETR}$. For every instance $\varPsi$ of Constrained-UETR, we give a set of points V and unordered triples T, along with a partial area assignment $\mathcal A'$. Let $\varPsi$ be a formula of the form: $\varPsi = (\forall Y_1, \ldots ,Y_m \in \mathbb {R} ^+ )(\exists X_1,\ldots ,X_n \in \mathbb {R} ^+) :\varPhi (Y_1, \ldots ,Y_m,X_1,\ldots ,X_n).$

Recall that $\varPhi$ is a conjunction of constraints of the form $X = 1$, $X+Y = Z$, and $X\cdot Y = Z$. First, we show how to express $\varPhi$. Our gadgets are similar to the ones for showing $\exists \mathbb {R}$-hardness of Order Type (see [12]). All variables are represented by points on one line; which we denote by $\ell$ for the rest of the proof. First, we enforce points to be on $\ell$. Afterwards we construct gadgets for mimicking addition and multiplication.

Introduce three points $p_0$, $p_1$, and r and define $\mathcal {A} '(p_0,p_1,r):=1$. The positive area ensures that the points are not collinear and pairwise different. Without loss of generality we assume that $\Vert p_0p_1\Vert =1$ and interpret $p_0$ as 0 and $p_1$ as 1. Denoting a line through two points a and b by $\ell _{a,b}$, we set $\ell := \ell _{p_0,p_1}$. To force a point x on $\ell$, we set $\mathcal {A} '(x,p_0,p_1):=0$. This introduces no other constraints on the position of x. Each variable X is represented by a point x on $\ell$. Additionally, since all variables are non-zero, we introduce a triangle forcing x to be different from $p_0$. In general, we can ensure that two points $x_1$ and $x_2$ are distinct, by introducing a point q and adding a triangle $(x_1,x_2,q)$ with $\mathcal {A} '(x_1,x_2,q):=1$. The absolute value of X is defined by $\Vert p_0x\Vert$; if x and $p_1$ lie on the same side of $p_0$, then the value of X is positive, otherwise it is negative. Here, we allow negative values, but later we force the original variables to be positive.

Now, we describe the addition gadget for a constraint $X+Y=Z$. Let x, y, z be the points encoding the values of X, Y, Z, respectively. Recall that $x,y,z\in \ell$ and $x,y,z\ne p_0$. We introduce a point $q_1$ and prescribe the areas $\mathcal {A} '(p_0,x,q_1)=\mathcal {A} '(y,z,q_1)=1$, see on the left of Fig. 4. Since the two triangles have the same height, it holds that $\Vert yz\Vert =\Vert p_0x\Vert$. Thus, the value of Z is either $X+Y$ or $X-Y$. Analogously, we introduce a point $q_2$ and define $\mathcal {A} '(p_0,y,q_2)=\mathcal {A} '(x,z,q_2)=1$, implying that Z is either $Y+X$ or $Y-X$. Therefore either $Z=X+Y$ (the intended solution) or $Z=X-Y=Y-X$. The latter case implies $X=Y$ and thus $Z=0$. This contradicts the fact that $z\ne p_0$.

Fig. 4.

Gadgets for addition and multiplication.

For the multiplication gadget, we show how to enforce on four pairwise different points $p,p',s,s'$ that $\ell _{p,p'}$ is parallel to $\ell _{s,s'}$, without introducing additional constraints on any of the four points. We insert two new points $h_1$ on line $\ell _{p,p'}$ and $h_2$ on line $\ell _{s,s'}$ by defining $\mathcal {A} '(p,p',h_1)=\mathcal {A} '(s,s',h_2)=0$. We aim for a trapezoid with points $p,h_1,s,h_2$ such that $ph_1$ is parallel to $sh_2$. For this, we prescribe the areas $\mathcal {A} '(p,h_1,s)=\mathcal {A} '(p,h_1,h_2)=1$ and $\mathcal {A} '(s,h_2,p)=\mathcal {A} '(s,h_2,h_1)=2$, see Fig. 5. Indeed, s and $h_2$ must lie on the same side of the line $\ell _{p,h_1}$: Assume by contradiction that $\ell _{p,h_1}$ separates s and $h_2$. If $p,h_1$ are on the same side of $\ell _{s,h_2}$ then the triangle $(s,h_2,p)$ is contained in or contains the triangle $(s,h_2,h_1)$, see the middle of Fig. 5. However this contradicts the fact that both triangles have the same area and $p \ne h_1$. Consequently, $\ell _{s,h_2}$ separates p and $h_1$ and the quadrangle $psh_1h_2$ can be partitioned by either diagonal $sh_2$ or $ph_1$. Thus, $2=\mathcal A (p,h_1,s)+ \mathcal A (p,h_1,h_2)=\mathcal A (s,h_2,h_1) +\mathcal A (s,h_2,p)=4$, which is again a contradiction. Thus $s,h_2$ lie on the same side of $\ell _{p,h_1}$. By the prescribed area, s and $h_2$ have the same distance to $\ell _{p,h_1}$. Hence, the segments $ph_1$ and $sh_2$ and the lines $\ell _{p,p'}$ and $\ell _{s,s'}$ are parallel and no further constraints are imposed $p,p',s,s'$.

Fig. 5.

Forcing a trapezoid.

To construct a multiplication gadget for the constraint $X \cdot Y = Z$, let $x,y,z\ (\ne p_0)$ be the points encoding the values of X, Y, Z, respectively. We introduce two points $p,p'$ not on $\ell$, but collinearity with $p_0$ is forced by $\mathcal {A} '(p_0,p,p'):=0$. By the parallel-line construction we force that $\ell _{p_1,p} \text { with } \ell _{y,p'} \text { and } \ell _{x,p} \text { with } \ell _{z,p'}$ are parallel, see Fig. 4. By the intercept theorem, the following ratios coincide (also for negative variables): $|p_0p|/|p_0p'|=|p_0p_1|/|p_0y|=|p_0x|/|p_0z|$. By definition of x, y, z, we obtain $1/Y = X/Z$, and hence $X \cdot Y = Z$. Recall that $p_1 = 1$. For every universally quantified $Y_i$, let $y_i$ be the point encoding its value with $y_i\in \ell$ and $y_i \ne p_0$. We introduce a triple $f_i = (p_0,r,y_i)$, whose area is universally quantified. Recall that r is a point with $\mathcal {A} '(p_0,p_1,r)=1$. To enforce each original variable X to be positive, we add an existentially quantified variable $S_X$ and the constraint $X = S_X \cdot S_X$ where $S_X$ may or may not be positive. This finishes the reduction which clearly runs in polynomial time.

It remains to argue that $\varPsi$ is true if and only if, for the constructed instance of Area Universality for Triples PA with partial assignment $\mathcal {A} '$, every assignment $\mathcal {A}$ consistent with $\mathcal {A} '$ is realizable. Suppose $\varPsi$ is true, let $\mathcal {A} '$ be as above, and consider an assignment $\mathcal {A}$ that is consistent with $\mathcal {A} '$. Let $V(Y_i)$ be the area assigned to the triple $f_i$, and let $V(X_i)$ be the value of the variable $X_i$ in some satisfying assignment for $\varPhi$. Let $y_1,\dots ,y_m,x_1,\ldots ,x_n$ be points positioned on a line at distances from a point $p_0$ corresponding to these values. Since addition and multiplication relations specified by $\varPhi$ hold, the corresponding gadgets can be realized, so $\mathcal {A}$ is realizable. Suppose that every assignment $\mathcal {A}$ that is consistent with $\mathcal {A} '$ is realizable and consider values $V(Y_1),\ldots ,V(Y_m) \in \mathbb {R} ^+$ of the universally quantified variables of $\varPsi$. Then there is a realization of $\mathcal {A}$ where $p_0 \ne p_1$ and each $f_i$ has area $V(Y_i)$. So $V(X_i) = \Vert x_i -p_0\Vert /\Vert p_1-p_0\Vert$ is a satisfying assignment for $\varPhi$, thus $\varPsi$ is true.    $\square$

4 Hardness of Prescribed Area PE

Here we sketch a proof of Theorem 2 by reducing from Planar-ETRINV.

Theorem 2

Prescribed Area PE is $\exists \mathbb {R}$-complete.

Proof

(Sketch). Let $\varPsi = \exists X_1\ldots X_n:\varPhi (X_1,\ldots ,X_n)$ be an instance of Planar-ETRINV. Recall that we can assume that if $\varPsi$ is a positive instance, then it has a solution in which the values of variables are in the interval (0, 5). We construct a plane graph $G_\varPsi =(V,E)$, a face area assignment $\mathcal A$ of inner faces of $G_\varPsi$, and fixed positions of a subset of vertices, such that $G_\varPsi$ has a realizing drawing respecting the position of pre-drawn vertices if and only if $\varPhi$ is satisfiable by real values from the interval (0, 5). Consider the incidence graph of $\varPhi$ and fix an orthogonal plane drawing on an integer grid, see Fig. 6 for an example.

Fig. 6.

Incidence graph of $(X_1+X_2=X_3) \wedge (X_1X_2 =1 ) \wedge (X_1 + X_4 = X_3) \wedge (X_4 X_3=1)$.

Fig. 7.

Gadgets for Theorem 2; black vertices are fixed, gray vertices are flexible.

To represent each part of $G_\varPsi$, we design several gadgets: variable gadgets to represent the variables, as well as inversion and addition gadgets to realize the constraints. Moreover, we construct wires and splitters in order to copy and transport information. For an illustration consider Fig. 7. Some vertices in our gadgets have prescribed positions; we call them fixed. The remaining vertices are flexible. Most flexible vertices lie on a specific segments where the distance to one end of the segment encodes the value of the variable.    $\square$

5 Volume-Universality

In order to show Theorem 3, we reduce from ETRINV and for Theorem 4 from Constrained-UETR. We construct a simplicial complex $\mathcal {S} =(V,F)$ and a volume assignment $\mathcal V$, such that $\mathcal {S}$ has a $\mathcal V$-realization iff $\varPhi$ is satisfiable. Our essential building block is the coplanar gadget. It forces several triangles of equal area to lie in a common plane, see Fig. 8 (left). These triangles will be free to one half-space and thus accessible for our further construction. Indeed, all but one vertices lie in the same plane. We use the coplanar gadget to force a set of points representing the values of the variables to lie on a common line $\ell$. In order to do so, we take two coplanar gadgets and enforce that their base planes $E,E_\ell$ are not parallel, see Fig. 8 (right). This allows us to mimic addition and inversion on a line as before. It turns out that in three dimensions we can guarantee crossing-free simplices.

Fig. 8.

Two gadgets for Prescribed Volume and Volume Universality PA.

6 Potential Complete Problems

To motivate the research on $\forall \exists \mathbb {R}$ and $\exists \forall \mathbb {R}$, we present some candidates of problems that might be complete for these classes. A very natural one was suggested by Marcus Schaefer. It is the well-known problem of determining the Hausdorff distance of two semi-algebraic sets: For two sets $A,B\subseteq \mathbb {R} ^d$, the Hausdorff distance $d_H$ is defined as $d_H(A,B) = \displaystyle \max \{ \sup _{a\in A} \inf _{b\in B} \Vert ab\Vert , \sup _{b\in B} \inf _{a\in A}\Vert ab\Vert \}$, where $\Vert ab\Vert$ denotes the Euclidean distance. As a step towards proving the $\forall \exists \mathbb {R}$-hardness of this problem, we show hardness for a variant where quantifier-free formulas describing the semi-algebraic sets are part of the input.

Given a quantifier-free formula $\varGamma$ of the first-order theory of the reals with n free variables, $S_\varGamma := \{x\in \mathbb {R} ^n : \varGamma (x)\}$ is the semi-algebraic set defined by $\varGamma$. By $\pi _k : \mathbb {R} ^n \rightarrow \mathbb {R} ^k$ we denote the projection onto the first k coordinates. Note that the complexity of a quantifier-free formula $\varGamma '$ defining $\pi _k(S_\varGamma )$ may exceed the complexity of $\varGamma$. In Hausdorff Distance of Projections, the input consists of two quantifier-free formulas $\varPhi$ and $\varPsi$ in the first-order theory of the reals and $k\in \mathbb {N}$. The question is whether $d_H(\pi _k(S_{\varPhi }),\pi _k(S_{\varPsi }))=0$.

Lemma 1

Hausdorff Distance of Projections is $\forall \exists \mathbb {R}$-complete.

Several other candidates of $\forall \exists \mathbb {R}$- and $\exists \forall \mathbb {R}$-complete problems are related to the notion of imprecision, where we assume that our input is only a rough approximation of the ‘real’ input. Nevertheless, we seek a universal solution that is valid in any case, i.e., for every possible realization of the imprecise data. As an example, consider Universal Guard Set, a variant of the Art Gallery Problem [1]. For a set of unit disks specifying the imprecise placement of polygon vertices, we ask for a minimum set of guards (points), that can guard every polygon formed by points from the unit disks.