Fixed Points, Nash Equilibria, and the Existential Theory of the Reals

Abstract

We introduce the complexity class $\exists \mathbb {R}$ based on the existential theory of the reals. We show that the definition of $\exists \mathbb {R}$ is robust in the sense that even the fragment of the theory expressing solvability of systems of strict polynomial inequalities leads to the same complexity class. Several natural and well-known problems turn out to be complete for $\exists \mathbb {R}$; here we show that the complexity of decision variants of fixed-point problems, including Nash equilibria, are complete for this class, complementing work by Etessami and Yannakakis [13].

1 Introduction

Many computational problems in geometry, graph drawing and other areas can be shown decidable using the (existential) theory of the real numbers, including the rectilinear crossing number, the Steinitz problem, and finding a Nash equilibrium; what is less often realized, though there are some exceptions, is that the existential theory of the reals captures the computational complexity of many of these problems precisely. In previous papers, the first author investigated some geometric problems related to graph drawing [30, 31]. In the current paper, we present tools to deal with semialgebraic and algebraic sets, such as effective lower bounds on the distance between two semialgebraic sets. These tools are useful in solving computational complexity problems related to the existential theory of the reals. We illustrate this by applying them to a variety of fixed point-problems and Nash equilibria, complementing work of Etessami and Yannakakis [13].

From an algebraic point of view, there are two ways to define the existential theory of the reals depending on whether we allow equality or not; for example, take the rectilinear crossing number, which is the smallest number of crossings in a straight-line drawing of a graph. The rectilinear crossing number problem can be expressed as a system of strict inequalities, and, as a consequence, a drawing realizing the rectilinear crossing number of a graph can be assumed to have vertices with rational coordinates (even if some of them may require exponential precision, see [4]); similarly, intersection graph problems can typically be captured by strict inequalities (for example, the problems in [30], including segment intersection graphs). On the other hand, fixed-point problems need equality to be modeled in the existential theory of the reals, and so their solution sets do not necessarily contain rational points: the fixed point of f(x)=2/x is $\sqrt {2}$. In Section 4 we prove the rather unexpected result that from a computational point of view, these two variants of the existential theory of the reals are the same, justifying the introduction of a single complexity class $\exists \mathbb {R}$. Section 2 reviews the logical and computational side of the existential theory of the reals, and Section 3 presents some tools based on algebraic geometry which turn out to be useful in handling problems in the class $\exists \mathbb {R}$. In Section 2 we then show that several fixed-point problems are complete for this class.

Since the class $\exists \mathbb {R}$ was first introduced (in an earlier version of this paper, as well as [30, 31]), there have been several new $\exists \mathbb {R}$-completeness results, including:

• straight-line realizability of abstract topological graphs (even the complete graph) [22],

• recognizing unit disk graphs and dot-product graphs [18],

• simultaneous geometric planarity [10],

• a data exchange problem for arithmetic schema mapping [35],

• stretchability of pseudocircles [19].

Together with the results from earlier papers this already gives us a sizable collection of complete problems for $\exists \mathbb {R}$ from many different areas (see [4, 8, 12, 20, 24, 27, 28, 32, 34], for example; a survey on the topic is in preparation [29]; there is a wikipedia page on $\exists \mathbb {R}$ [39]).

We assume that the reader is familiar with basic notions of computational complexity, including polynomial time, polynomial-time many-one reducibilities and complexity classes such as NP, and PSPACE [25, 33].

2 The Existential Theory of the Reals

The existential theory of the reals, ETR, is the set of true sentences of the form

$$(\exists x_{1}, \ldots, x_{n})\ \varphi(x_{1}, \ldots, x_{n}), $$

where φ is a quantifier-free (∨,∧,¬)-Boolean formula over the signature (0,1,+,∗,<,≤,=) and the sentence is interpreted over the universe of real numbers.¹

In a 1948 paper entitled “A Decision Method for Elementary Algebra and Geometry”, Alfred Tarski proved a quantifier elimination result for the existential theory of the reals, which implied that the theory of the reals, with arbitrary quantifiers, is decidable. In his 1988 dissertation, Canny showed that ETR can be decided in PSPACE, to date the best theoretical upper bound on ETR. For a recent survey, see [23], for experimental comparisons of running times, see [15].

We will find it useful to distinguish two special cases of ETR. Let INEQ be the subset of ETR, in which we do not allow ∨,¬ and =, that is φ is a conjunction of atoms of the form s < t and s ≤ t (s = t can be expressed as s ≤ t∧t ≤ s so not allowing equality is not a real restriction). Furthermore, let STRICT INEQ be the subset of INEQ, in which we do not allow ≤, that is, φ is a conjunction of strict inequalities s < t.

Following our first impulse as complexity theorists we use STRICT INEQ and INEQ to define complexity classes $\exists \mathbb {R}$ and NPRE as the downward closures of these problems under polynomial-time many-one reductions; with this definition $\exists _{<}\mathbb {R} \subseteq \exists _{=}\mathbb {R}$ and there seems to be evidence that these two classes are different: solutions to an INEQ-type problem can require irrational numbers, e.g. x ²=2, while solutions to STRICT INEQ can always be perturbed slightly to make them rational. These differences are of an algebraic nature and, in a slightly surprising twist of events, do not affect the computational complexity of these problems. It turns out that $\exists _<\mathbb {R} = \exists _=\mathbb {R}$ as we will see in Section 4. In other words, INEQ polynomial-time many-one reduces to STRICT INEQ.

Note that NP $\subseteq \exists _<\mathbb {R}$ (a result first explicitly stated by Shor [32]), since we can express satisfiability of a Boolean formula in $\exists _<\mathbb {R}$. For example, $\varphi = (x \vee \overline {y} \vee z) \wedge (\overline {x} \vee y \vee z) \wedge (\overline {x} \vee \overline {y} \vee \overline {z})$ is equivalent to

$$\begin{array}{@{}rcl@{}} \lefteqn{(\exists x, y, z, \varepsilon) [\ (-\varepsilon < x < 1+\varepsilon) \wedge (-\varepsilon < y < 1+\varepsilon) \wedge (-\varepsilon < z < 1+\varepsilon)} \\ && \wedge\ (x (1-y) z) + ((1-x) y z) + ((1-x)(1-y) (1-z)) < \varepsilon, \\ && \wedge\ \varepsilon > 0 \wedge\ \varepsilon < 1/104 ]. \end{array} $$

If the formula is satisfiable, then we assign a variable the value 0 if it is true and 1 otherwise, so that the sum becomes 0<ε; in the example: x = y=0 and z=1 will do. For the reverse direction, assume x,y,z, and ε satisfy the formula. Note that 0<ε<1/104=1/8(1+4m), where m=3 is the number of clauses. Each term of the sum is at least −ε⋅(1 + ε)²≥−4ε; so the whole sum is at least −4m ε≥−12/104. For the sum to be less than 1/104, every term must be less than 1/104+12/104=1/8. Each term is the product of three factors, so at least one factor must be less than (1/8)^1/3=1/2. Let the corresponding variable be true if the factor is of the form x and false if it is of the form 1−x. This yields a satisfying assignment of the original Boolean formula φ.

So, with respect to classical complexity classes, we can summarize our present knowledge of the existential theory of the reals by

$$\text{NP} \subseteq \exists_<\mathbb{R} \subseteq \exists_=\mathbb{R} \subseteq \text{PSPACE}, $$

where the last implication is due to Canny’s result [9].

Remark 2.1 (Models of Real Computation)

We are not treating the existential theory of the real numbers as a model of real computation in two senses: there are no “real” real numbers in ETR (other than rationals), and we do not present a machine model for the classes $\exists _<\mathbb {R}$ and $\exists _=\mathbb {R}$. It turns out that it is possible to construct a machine model for $\exists _=\mathbb {R}$; this was essentially done by Blum, Shub, and Smale [6] whose results imply that the languages in {0,1}^∗ decided by a real non-deterministic polynomial-time Turing machine that has no registers for real numbers are precisely the languages in $\exists _=\mathbb {R}$.² This connection between ETR and the BSS-model does not give any insights on the problems dealt with in the current paper, which is why we do not discuss this (or other models of real computation) any further. However, the BSS-model could be a first step toward more structural results such as oracle separations.

3 Semi-Algebraic Sets of Bounded Complexity

Our goal in this section is to collect a couple of tools for dealing with semi-algebraic sets of bounded complexity. In particular, we want to show that such sets always contain a point not too far from the origin (Corollary 3.4), that we can find a ball that contains a bounded semi-algebraic set (Corollary 3.7), and that there is a lower bound on the distance between two semi-algebraic sets that have positive distance (Corollary 3.8).

We will use the following notations throughout this paper: [n] as an abbreviation for the set {1,…,n}, $\|x\|^{2} := {\sum }_{i \in [n]} {x_{i}^{2}}$ is the square of the distance of x from the origin, the distance d(A,B) between two sets $A, B \subseteq \mathbb {R}^{n}$ is defined as d(A,B)= inf{d(a,b):a∈A,b∈B}, where ∥a−b∥ is the Euclidean distance between two points. The bitlength of an integer n is the smallest number b(n) of bits to write down the number in binary digits. So b(n)=⌊(log2(n)⌋+1 for n≥1 and b(0)=1. In particular, n<2^b(n) for all n.

3.1 Definitions and Basic Results

In algebraic geometry semi-algebraic sets are solution sets to systems of polynomial equalities and inequalities; taking a more logical approach, we say a set $S \subseteq \mathbb {R}^{n}$ is semi-algebraic if there is a (∨,∧,¬)-Boolean quantifier-free formula over the signature (0,1,+,∗,<,≤,=) and with (free) variables x=(x ₁,…,x _n ) so that $S = \{x \in \mathbb {R}^{n}: \varphi (x)\}$. If φ does not contain ∨ or ¬, we call the set a basic semi-algebraic set. If, moreover, φ does not contain < and ≤, the set is algebraic. We use |φ| to denote the length of φ, that is, the number of bits necessary to write down φ. The (bit)-complexity of a semi-algebraic set is the shortest length of any formula defining the set.

In algebraic geometry, semi-algebraic sets are defined as finite unions of basic semi-algebraic sets; since we gave a definition via defining formulas, we have to prove that result. We also show that the complexity of the basic semi-algebraic sets need be no larger than the complexity of the original set.

Lemma 3.1

Every semi-algebraic set of complexity at most L is the finite union of basic semi-algebraic sets each of complexity at most L. We can assume that the defining formula of each of the basic semi-algebraic sets does not contain the comparison operator ≤.

Proof

Let φ be a formula of bitlength at most L defining the semi-algebraic set $S = \{x: \mathbb {R}^{n}: \varphi (x)\}$. If φ contains any negations, we push them to the lowest level of the formula, and absorb them in the atomic formulas: $\overline {s<t}$ becomes t ≤ s, $\overline {s\leq t}$ becomes t < s, and $\overline {s=t}$ turns into s < t∨t < s. Replace all inequalities of type s ≤ t by s < t∨s = t and convert the resulting formula ψ into disjunctive normal form: $\psi = \bigvee _{i \in I} \psi _{i}$ for some $I \subseteq \mathbb {N}$. Then each ψ _i defines a basic semi-algebraic set (not using ≤), and S is the union of these sets. Each ψ _i uses at most one clause of each disjunction we introduced when rewriting s ≤ t and $\overline {s=t}$, so each of its clauses stems from a different clause in the original φ and so |ψ _i |≤|φ|. □

The following lemma gives us a way to replace the defining formula of a semi-algebraic set with a single multivariate polynomial. Multivariate polynomials are sums (or differences) of monomials, the complexity of a polynomial is the number of bits needed to write it down in this form; this means, that while we may write (x+1)(y+1) to simplify notation, the polynomial has to be written out as x y + x + y+1 explicitly. Other measures of complexity for polynomials include bounds on the bitlength of the coefficients (as integers) of monomials, typically written as τ, and the (total) degree of the polynomial f which is defined as the maximum over the sum of the variable exponents in each monomial term occurring in f. E.g. f(x,y,x)=5x ⁷ y ²−2x ³ y z ⁶ has total degree 3+1+6=10.

Lemma 3.2

If S is a semi-algebraic set in $\mathbb {R}^{n}$ given by a formula φ of complexity at most L≥3, then we can efficiently (that is in time polynomial in L and n) construct

• a family of quadratic polynomials $f_{j}: \mathbb {R}^{n+m} \rightarrow \mathbb {R}$ , j∈[k], so that $S = \{x \in \mathbb {R}^{n}: (\exists y \in \mathbb {R}^{m}) \bigwedge _{j\in [k]} f_{j}(x,y) = 0\}$, for some m,k≤3L,

• a non-negative polynomial $g: \mathbb {R}^{n+m} \rightarrow \mathbb {R}$ of degree at most 4 so that $S = \{x \in \mathbb {R}^{n}: (\exists y \in \mathbb {R}^{m})\; g(x,y) = 0\}$ , for some m≤3L.

The coefficients of the polynomials f _j have bitlength at most L and coefficients in g have bitlength at most 2L.

This lemma is an efficient version of the well-known fact that every semi-algebraic set is the projection of an algebraic set (the set of zeros of a polynomial). Similar to the situation in the Blum-Shub-Smale model of real computation, it is unlikely that the degree of g can be reduced below 4, since it can be decided in polynomial time whether a polynomial of degree at most 3 has a zero [36].

Proof Proof of Lemma 3.2

Clearly, (i) implies (i i): with the family f from (i), define $g(x,y) = \sum \limits _{1 \leq j \leq k} (f_{j}(x,y))^{2}$. Then f _j (x,y)=0 for all j∈[k] if and only if g(x,y)=0, and the bitlength of coefficients at most doubles. Note that g is non-negative. Hence, it is sufficient to prove (i). Let $S = \{x \in \mathbb {R}^{n}: \varphi (x)\}$, where φ has complexity at most L. As in Lemma 3.1, push all negations to the atomic level, and replace $\overline {s<t}$ with t ≤ s, $\overline {s\leq t}$ with t < s, and $\overline {s=t}$ with s < t∨t < s. This at most doubles the length of φ. We now use a trick based on an idea due to Tseitin [21, 37], to build quadratic polynomials f _j (x,y) with new variables $y \in \mathbb {R}^{m}$, for some m, so that $\varphi (x) \equiv (\exists y)\bigwedge _{j\in [k]}\; f_{j}(x,y) = 0$.

For any subformula γ of φ create a new real variable y _γ and, as needed, $y^{\prime }_{\gamma }$ and $y^{\prime \prime }_{\gamma }$. For any subterm s of φ create a new real variable y _s . We will ensure that for any x, y with the property that f _i (x,y)=0 for every i∈[k], we have that y _s = s and that if y _γ =0, then γ(x) is true. The variables $y^{\prime }_{\gamma }$ and $y^{\prime \prime }_{\gamma }$ are needed for intermediate calculations only.

To simplify notation, we index the family of polynomials f using subformulas and subterms of φ. Let s be any subterm of φ. If s = t∘u, we define f _s (x,y) = s−(t∘u) (where ∘∈{+,−,∗}); if s = x _i , we define f _s (x,y) = s−x _i

Let γ be any subformula of φ. If γ = α∨β, we define f _γ (x,y) = y _γ −y _α y _β ; if γ = α∧β, we define $f_{\gamma }(x,y) = y_{\gamma } - (y^{2}_{\alpha } + y^{2}_{\beta })$. If γ=(s = t), we define f _γ (x,y) = y _γ −(y _s −y _t ). If γ=(s < t), we need to define two polynomials, let us call them f _γ,0, and f _γ,1; we define $f_{\gamma ,0}(x,y) = y^{\prime }_{\gamma } - (y^{\prime \prime }_{\gamma })^{2}$, and $f_{\gamma ,1}(x,y) = (y_{t}-y_{s})y^{\prime }_{\gamma } - (1-y_{\gamma })$. Note that if $f_{\gamma ,0}(x,y) = f_{\gamma _{1}}(x,y)=0$ and y _γ =0, then $y^{\prime }_{\gamma } \geq 0$ and 1−y _γ =1, so y _t >y _s ; the reverse need not be true.

Now, if φ(x) is true, then by construction, we can choose values for y _s , y _γ , $y^{\prime }_{\gamma }$ and $y^{\prime \prime }_{\gamma }$ so that for all j we have f _j (x,y)=0. If, on the other hand, for all j we have f _j (x,y)=0, then all the terms f _γ and f _s are zero. In particular, y _φ =0, so, γ is true (since this implication holds for each step of the recursive construction of y _φ ).

The degree of the polynomials in f are at most 2, and the bitlengths of coefficients was not increased by the construction. Since a formula φ of length L can have at most L subformulas and subterms, we conclude that k≤2L (at most two polynomials per subformula), and m≤3L (at most three variables per subformula). □

3.2 Main Tools

The three main corollaries in this Section 3.4, 3.7 and 3.8 are based on corresponding results from algebraic geometry on systems of polynomial equalities and inequalities. For example, Vorobjov [38] and Grigor’ev and Vorobjov [14] were the first to show that every semi-algebraic set of complexity at most L contains a point of distance at most $2^{2^{O(L)}}$ from the origin.³ We use a more recent result due to Basu and Roy [3] which gives explicit constants (which may be of interest in applications).⁴

Theorem 3.1 (Basu, Roy [3, Theorem 4])

Let (f _i ) _i∈[s] be a family of polynomials of type $\mathbb {R}^{n} \rightarrow \mathbb {R}$ all of degree at most d and with coefficients of bitlength at most τ. Define

$$R = \left( (2DN(2N -1) +1) 2^{(2N-1)(\tau^{\prime}+ b(2N-1) +b(2DN+1))}\right)^{1/2}, $$

with d ^′ = max(2(d+1),6), D=n(d ^′ −2)+2, N=d ^′ (d ^′ −1) ⁿ⁻¹ , τ ^′ =N(τ ₂ +b(N)+2b(2D+1)+1), τ ₂ =τ ₁ +2(n−1)b(N)+(2n−1)b(n), τ ₁ =D(τ ₀ +4b(2D+1)+b(N))−2b(2D+1)−b(N), τ ₀ =2τ+nb(d+1)+b(2d ^′ )+b(s). Then a ball of radius R around the origin contains a point of every semi-algebraic set $S = \{x \in \mathbb {R}^{n}: f_{i}(x) \triangle _{i} 0\}$ that can be defined by choosing △ _i ∈{>,<,=}.

These estimates are much finer than what is needed for our purposes, since we are only bounding the overall complexity of the formula. Deriving the following bound is tedious, but straightforward, the details can be found in Appendix A.

Corollary 3.1

Every semi-algebraic set in $\mathbb {R}^{n}$ of complexity at most L≥4 contains a point of distance at most $2^{L^{8n}}$ from the origin.

The remaining two corollaries we base on a result by Jeronimo and Perrucci who showed that a positive polynomial (all values are greater than 0) defined over a simplex can be bounded away from 0.⁵ Let ${\Delta }_{n} = \{x \in \mathbb {R}_{\geq 0}^{n}$ with ${\sum }_{i \in [n]} x_{i} \leq 1\}$ be the standard simplex in $\mathbb {R}^{n}$.

Theorem 3.2 (Jeronimo, Perruci [16])

If $f: \mathbb {R}^{n} \rightarrow \mathbb {R}$ is a polynomial of degree d so that f(x)>0 for all x∈Δ _n , and all coefficients of f have bitlength at most τ, then

$$f(x) > 2^{-(\tau+1)d^{n+1}}d^{-(n+1)d^{n+1}} $$

for all x∈Δ _n .

The obvious generalization from Δ _n to $\mathbb {R}^{n}$ fails; for example, f(x,y) = x ²+(1−x y)² is positive for all $x,y \in \mathbb {R}$ but cannot be bounded away from 0. Instead, we require that we know that f is bounded away from 0.

Corollary 3.2

If $f: \mathbb {R}^{n} \rightarrow \mathbb {R}$ is a polynomial of degree d so that f(x)≥δ>0 for all $x \in \mathbb {R}^{n}$ and some fixed δ, and all coefficients of f have bitlength at most τ, then

$$f(x) > 2^{-(\tau n^{d}+1)d^{n+1}}d^{-(n+1)d^{n+1}} $$

for all $x \in \mathbb {R}^{n}$.

Proof

Let ${\Delta }^{\prime }_{n} = \{y \in \mathbb {R}_{\geq 0}^{n}: {\sum }_{i \in [n]} y_{i} < 1\}$ and define $r(y) = y/(1-{\sum }_{i \in [n]} y_{i})$ for $y \in {\Delta }^{\prime }_{n}$. Then r is a homeomorphism between ${\Delta }^{\prime }_{n}$ and $\mathbb {R}_{\geq 0}^{n}$. Let $f(x) = {\sum }_{j \in J} a_{j} x^{j}$, where $J \subseteq {\mathbb {N}}^{n}$ and $x^{j} := x_{1}^{j_{1}} {\cdots } x_{n}^{j_{n}}$. The function f∘r is a rational function and can be written as f(r(y)) = g(y)/h(y), where $g(y) = {\sum }_{j \in J} a_{j} y^{j} (1-{\sum }_{i \in [n]} y_{i})^{d-({\sum }_{i \in [n]} j_{i})}$ and $h(y) = (1-{\sum }_{i \in [n]} y_{i})^{d}$. We see that both g and h are polynomials of degree at most d, and the bitlength of their coefficients is bounded by τ ^′ = n ^d τ. Now for $y\in {\Delta }^{\prime }_{n}$ we have h(y)≤1 and, by Theorem 3.5, $g(y) > 2^{-(\tau ^{\prime }+1)d^{n+1}}d^{-(n+1)d^{n+1}} = 2^{-(\tau n^{d}+1)d^{n+1}}d^{-(n+1)d^{n+1}}$. Therefore, $f(r(y)) = g(y)/h(y) \geq g(y) \geq 2^{-(\tau n^{d}+1)d^{n+1}}d^{-(n+1)d^{n+1}}$ for all $y \in {\Delta }^{\prime }_{n}$. Hence $f(x)\geq 2^{-(\tau n^{d}+1)d^{n+1}}d^{-(n+1)d^{n+1}}$ for all $x\in \mathbb {R}_{\geq 0}^{n}$. By modifying the definition of r we can establish this lower bound on f for each of the hyperoctants of $\mathbb {R}^{n}$ proving the result. □

We derive two further consequences from Corollary 3.6: an upper bound (in terms of distance) on all points in a bounded semi-algebraic set, and a lower bound on the distance between two semi-algebraic sets that have a positive distance.

Corollary 3.3

If a bounded semi-algebraic set in $\mathbb {R}^{n}$ has complexity at most L≥5n, then all its points have distance at most $2^{2^{L+5}}$ from the origin.

There is a finer bound in terms of n, d, and τ due to Basu and Roy [3].

Proof Proof of Corollary 3.7

Let $S = \{x \in \mathbb {R}^{n}: \varphi (x)\}$, where φ has complexity at most L, be a bounded semi-algebraic set. Then R= supx∈S∥x∥²<∞. By Lemma 3.2, there is a polynomial g of degree at most 4 with coefficients of bitlength at most 2L, so that $S = \{x \in \mathbb {R}^{n}: (\exists y \in \mathbb {R}^{m})\; g(x,y) = 0\}$. Let $f: \mathbb {R}^{n+m+1} \rightarrow \mathbb {R}$ be the polynomial defined by f(x,y,u) = u ²+(u∥x∥²−1)² + g(x,y). Then f has degree at most 4 and coefficients of bitlength at most 2L. Moreover, infx,y,u f(x,y,u)≤1/R ²: Let x ^(j) be a sequence of points in S such that ∥x ^(j)∥² converges to R. Then for each x ^(j) there is a y ^(j) so that g(x ^(j),y ^(j))=0. Then f(x ^(j),y ^(j),1/R)=1/R ²+(∥x ^(j)∥²/R−1)² which tends to 1/R ² as j→∞. By Corollary 3.6, f can be bounded below by

$$\begin{array}{@{}rcl@{}} 2^{-(\tau n^{d}+1)d^{n+1}}d^{-(n+1)d^{n+1}} \geq 2^{-(\tau n^{4} + 2n + 3)4^{n+1}} \geq 2^{-2^{L+6}}, \end{array} $$

where we used d≤4 in the first inequality, and τ≤2L and n ≤ L/5 in the second. Since (1) is a lower bound on 1/R ², we get $R^{2} \leq 2^{2^{L+6}}$ and hence $R \leq 2^{2^{L+5}}$. □

The second consequence is a lower bound on the distance between two semi-algebraic sets.

Corollary 3.4

If two semi-algebraic sets in $\mathbb {R}^{n}$ each of complexity at most L≥5n have positive distance (for example, if they are disjoint and compact), then that distance is at least $2^{-2^{L+5}}$.

Jeronimo, Perrucci, Tsigaridas [17, Theorem 2] give bounds on the minimum distance between two semi-algebraic sets in terms of n, τ and d, which is more than we need. Their result makes the stronger assumption that one of the two sets be compact.

Proof Proof of Corollary 3.8

Let $S = \{x \in \mathbb {R}^{n}: \varphi (x)\}$ and $T = \{x \in \mathbb {R}^{n}: \psi (x)\}$ so that φ and ψ have complexity at most L. We can assume that both S and T are non-empty. By Lemma 3.1 both S and T are the finite union of basic semi-algebraic sets of complexity at most L, so we can choose basic semi-algebraic subsets of S and T that realize the minimum distance. So let us assume that S and T are basic. Lemma 3.2 gives us polynomials g and h each of degree at most 4 and with coefficients of bitlength at most 2L so that $S = \{x \in \mathbb {R}^{n}: (\exists y \in \mathbb {R}^{m})\; g(x,y) = 0$ and $T = \{x: \mathbb {R}^{n}: (\exists y \in \mathbb {R}^{m})\; h(x,y) = 0\}$ (we can pad y if necessary so m is the same and g and h have the same number of variables). Consider the polynomial f(x,y,x ^′,y ^′) = g(x,y) + h(x ^′,y ^′)+∥x−x ^′∥². Then $\inf _{x,x^{\prime },y,y^{\prime }} f(x,y,x^{\prime },y^{\prime })$ is a lower bound on the square of the distance between S and T (pick x in the closure of S and x ^′ in the closure of T so that d(x,x ^′) = d(S,T), then choose sequences of elements in S and T converging to x and x ^′, with corresponding choices of y and y ^′). Since f has degree d≤4≤2L and its coefficients have bitlength τ≤2L as well, Corollary 3.6 implies that f has a lower bound of $2^{-2^{L+6}}$ (just as in Eq. 1 above, using the same estimates). Since this is a lower bound on the square of the distance which is less than 1, $2^{-2^{L+5}}$ is a lower bound on the distance. □

4 The Complexity Class $\exists \mathbb {R}$

We have defined three variants of the existential theory of the reals, ETR, INEQ, and STRICT INEQ; in this section we will show that they are all computationally equivalent. In particular, it will follow that NPRS = NPRE, which is a bit of a surprise, since algebraically these two classes differ. For the proof, we will use an intermediate problem FEAS which restricts ETR to formulas not containing ≠, ∨, ∧, < and ≤; in other words, FEAS asks whether a multivariate polynomial is feasible, that is, has a root over the reals.

Theorem 4.1

The following problems are polynomial-time equivalent: ETR, FEAS, STRICT INEQ.

Proof

In slightly different language, we already saw that ETR reduces to FEAS, that was what we proved in Lemma 3.2. Since STRICT INEQ is a special case of ETR, we are left with the proof that FEAS reduces to STRICT INEQ.

So suppose we are given a multivariate polynomial g and ask whether there is an $x \in \mathbb {R}^{n}$ so that g(x)=0. Let L be the complexity of g (recall that this is the number of bits required to write down g as a sum of monomials). By Corollary 3.4 we know that if $S = \{x \in \mathbb {R}^{n}: g(x) = 0\}$ is not empty, it contains a point of distance at most $R = 2^{L^{8n}}$ from the origin. Consider the two semi-algebraic sets $\{(z,x) \in \mathbb {R}^{n+1}: g(x) = z, \|x\|^{2} \leq R^{2}\}$ and $\{(z,x)\in \mathbb {R}^{n+1}: z=0, \|x\|^{2} \leq R^{2}\}$. If these two sets do not intersect, they have positive distance (both being compact), and, by Corollary 3.8, that distance is at least $2^{-2^{L+5}}$. Hence, g=0 is equivalent to the system

$$-\delta < g(x), g(x) < \delta, \delta < 2^{-2^{L+5}}, \|x\|^{2} \leq R^{2} $$

of strict inequalities being solvable. The inequality $\delta < 2^{-2^{L+5}}$ can be replaced by a sequence of at most L+5 inequalities using repeated squaring, so we have shown that FEAS can be reduced to STRICT INEQ. Note that this reduction does not (and cannot) maintain the realization space of the system (the set of solutions). □

As a corollary of Theorem 4.1 we obtain:

Corollary 4.1

$\exists _< \mathbb {R} = \exists _= \mathbb {R}$.

The corollary allows us to simplify our notation and call our new complexity class simply $\exists \mathbb {R}$. Our computational world now looks as follows:

$$\mathbf{NP} \subseteq \exists \mathbb{R} \subseteq \mathbf{PSPACE}. $$

Remark 4.1

Following standard usage, we will say a problem is $\exists \mathbb {R}$ -hard, if every problem in $\exists \mathbb {R}$ polynomial-time many-one reduces to it; it is $\exists \mathbb {R}$-complete, if it is $\exists \mathbb {R}$-hard and belongs to $\exists \mathbb {R}$. The complements of problems in $\exists \mathbb {R}$ can be said to belong to $\forall \mathbb {R}$, or $\textit{co} {\exists \mathbb {R}}$ (used in [35]).

Let QUAD be the computational problem asking whether a family of quadratic polynomials $f_{i}: \mathbb {R}^{n} \rightarrow \mathbb {R}$, i∈[k], has a common zero, and let 4-FEAS be the special case of FEAS in which the polynomial has degree at most 4. The algebraic versions of these problems are known to be hard for $\text {NP}_{\mathbb {R}}$, the analogue of NP in the Blum-Shub-Smale model [5, Section 5.4].

Corollary 4.2

QUAD and FFEAS are $\exists \mathbb {R}$ -complete.

In [31, Lemma 3.9] it is shown (assuming Corollary 4.4) that QUAD remains $\exists \mathbb {R}$-complete if we ask for a common zero in the unit ball B _n (0,1).

Proof

Lemma 3.2 shows that ETR reduces to QUAD, which in turn reduces to FFEAS. Obviously, both problem belong to $\exists \mathbb {R}$. □

Ten Cate, Kolaitis and Othman [35] recently showed that $\exists \mathbb {R}$ is downward closed under NP-reductions, that is, if a problem NP-reduces to a problem in $\exists \mathbb {R}$, then it also belongs to $\exists \mathbb {R}$, where an NP-reduction is a many-one reduction computed by a non-deterministic polynomial time Turing machine. This allows the authors to show that the data exchange problem they are interested in lies in $\exists \mathbb {R}$. They show $\exists \mathbb {R}$-completeness by reducing the rectilinear crossing number problem to the data exchange problem.

Let us mention one more tool that may be useful in showing some problem lies in $\exists \mathbb {R}$; the first author used this result in [31] (without proof) to show that non-rigidity of linkages lies in $\exists \mathbb {R}$.

Lemma 4.1

Let

$${\Phi}(\varepsilon, y) = (\exists x)\ \varphi(\varepsilon, x,y), $$

with ε>0, $x \in \mathbb {R}^{k}$ , $y \in \mathbb {R}^{\ell }$ , be such that Φ(ε,y) implies Φ(ε ^′ ,y) for all ε ^′ >ε. Then we can find a quantifier-free formula ψ(ε,x,y,z), with $z \in \mathbb {R}^{m}$ , of length at most |φ|+dm, where m=|φ|+5 so that

$$(\forall \varepsilon > 0)(\exists x)\ \varphi(\varepsilon,x,y) $$

is equivalent to

$$(\exists \varepsilon > 0, x, z)\ \psi(\varepsilon, x,y, z). $$

Proof

We assume $y \in \mathbb {R}^{\ell }$ is fixed and will drop it from the formulas (that is, we really prove the case ℓ=0).

Define two sets $A := \{(\varepsilon , x) \in \mathbb {R}^{k+1}: \varphi (\varepsilon , x), \varepsilon > 0\}$ and $B:= \{0\} \times \mathbb {R}^{k}$. If d(A,B)=0, then for every δ>0 there must be an ε so that δ>ε>0 and (ε,x)∈A for some x which, by monotonicity, implies that (ε ^′,x)∈A for all ε ^′>ε. Since δ can be chosen arbitrarily small, this means that (∀ε>0)(∃x) φ(ε,x) is true.

Otherwise, d(A,B)>0 and, by Corollary 3.4, $d(A,B) > 2^{-2^{L+5}}$. By construction, d(A,B) is a lower bound on the infimum over all ε>0 for which there is an x so that φ(x) is true; hence, φ(ε,x) is false for all x and all $\varepsilon < 2^{-2^{|\varphi |+5}}$, so (∀ε>0)(∃x) φ(ε,x) is false.

In other words, the truth of (∀ε>0)(∃x) φ(ε,x) is equivalent to $(\exists \varepsilon > 0)(\exists x)\ [\varphi (\varepsilon ,x) \wedge \varepsilon < 2^{-2^{L+5}}]$. Using repeated squaring, $\varepsilon < 2^{-2^{|\phi |+5}}$ can be expressed using a formula with at most m=|φ|+6 variables z. Combining this formula with φ(ε,x) we obtain ψ(ε,x,z) so that the conclusion of the lemma holds. □

To see how this lemma can be useful, we give two examples, the first is from [31]. Let ISO be be the problem of deciding whether a point $x \in \mathbb {R}^{n}$ is an isolated zero of a family (f _i ) _i∈[s] of multivariate polynomials. Then ((f _i ) _i∈[s],x) is not an instance of ISO, if x is not a zero of (f _i ) _i∈[s] or $(\forall \varepsilon > 0)(\exists y)\ [\sum \limits _{i \in [n]} (x_{i}-y_{i})^{2} < \varepsilon \wedge \bigwedge _{i \in [s]} f_{i}(y) = 0]$. By Lemma 4.5 the monotone all-quantification over ε can be replaced with an existential quantifier, and we conclude that $\overline {\text {ISO}}$ belongs to $\exists \mathbb {R}$; in other words ISO belongs to $\forall \mathbb {R}$.

Our second example is new:

Lemma 4.2

Deciding whether two semi-algebraic sets have distance zero is $\exists \mathbb {R}$ -complete.

It is tempting to conjecture that the condition is equivalent to the closure of the two algebraic sets having a non-empty intersection, but that is not correct, as the earlier example f(x,y) = x ²+(1−x y)² and g(x,y)=0 shows.

Proof

$\exists \mathbb {R}$-hardness is an obvious reduction from FEAS: a multivariate polynomial $f: \mathbb {R}^{n} \rightarrow \mathbb {R}$ has a zero if and only if $\{(x,y) \in \mathbb {R}^{n+1}: y = f(x), \|x\| \leq R\}$ and $\{(x,0) \in \mathbb {R}^{n+1}: \|x\| \leq R\}$ have distance 0, where R is an upper bound on a zero of f (use Corollary 3.1 applied to $\{x \in \mathbb {R}^{n}: f(x) = 0\}$).

The interesting part is showing that the problem lies in $\exists \mathbb {R}$. Using Lemma 4.5 this is easy now, because we can express that two semi-algebraic sets defined by polynomials f(x,y) and g(x,y) (use Lemma 3.2) have distance 0 as (∀ε > 0)(∃x,y,x ^′,y ^′)[f(x,y)=0∧g(x ^′,y ^′)=0∧∥x−x ^′∥≤ε]. □

5 Fixed Points and the Nash Equilibrium

How hard is it to find a fixed point of a function? Consider a simple version of that problem called FIXED in which we ask whether a family f of polynomials $f_{i}: \mathbb {R}^{n} \rightarrow \mathbb {R}$, i∈[n], has a fixed point, that is an $x \in \mathbb {R}^{n}$ so that f(x)=(f ₁(x),…,f _n (x)) = x. FIXED is $\exists \mathbb {R}$-complete: Obviously, it is a special case of INEQ, and we can reduce FEAS to it, since $g: \mathbb {R}^{n} \rightarrow \mathbb {R}$ has a zero, if and only if the family of polynomials defined by f _i (x) = g(x) + x _i has a fixed point.

In this section we consider continuous functions from a convex, compact set to itself. Such functions always have a fixed point by the Brouwer Fixed-Point Theorem, trivializing the question we asked for FIXED, but also giving a first hint that encoding is going to be harder with these functions. There are several computational questions that can be asked for this problem (see the detailed discussion by Etessami and Yannakakis [13]). We start with the decision version of the problem and discuss variants and the Nash Equilibrium problem in Section 5.2.

5.1 The Brouwer Fixed-Point Problem

Brouwer’s fixed point theorem implies that a continuous function from a convex compact set to itself has a fixed point. We are interested in the computational complexity of deciding whether there is a fixed point of the function in a given neighborhood. To slightly simplify the argument, we work over the domain B _n (x,r), the closed ball around $x \in \mathbb {R}^{n}$ of radius r in the ℓ ^∞-metric; in other words, B _n (x,r) is an n-dimensional box; for example, B _n (0,1/2) is the unit cube centered at the origin.

There are several choices for what continuous functions we allow. Typically, functions defined using straight-line programs (a very compact representation of polynomials) or even extended straight-line programs (a compact representation of a class of functions that includes all rational functions) are allowed in this context (see [13], for example). Since we want to show that the problem is hard, we obtain a stronger result, the more limited our set of continuous functions, so we settle on the set of polynomials, represented explicitly, that is, in the form $f(x) = {\sum }_{i \in I} c_{i} x^{i}$, where $x\in \mathbb {R}^{n}$, $I \subseteq {\mathbb {N}}^{n}$, $c_{i} \in \mathbb {Q}$, and $x^{i} = (x_{1}^{i_{1}}, \ldots , x_{n}^{i_{n}})$. We even restrict c _i to the set of values {−1,−1/2,0,1/2,1}. We can now define the computational version of the Brouwer fixed-point problem:

BROUWER

Given::

A polynomial family f:B _n (0,1)→B _n (0,1), represented explicitly, $x \in \mathbb {Q}^{n}$, $r \in \mathbb {Q}$.

Question::

Does f have a fixed point in B _n (x,r)?

Our goal is to show that BROUWER is $\exists \mathbb {R}$-hard. The strategy for the proof is simple: reduce the fixed-point problem FIXED to BROUWER. To encode FIXED, we need to scale the computations, since f has to take values in B _n (0,1). This is rather hard to achieve with explicitly represented polynomials, but becomes much easier if we use the (extended) straight-line representation. Consequently, the proof is in two parts: we show that (1) FIXED reduces to a fixed-point problem for extended straight-line programs (Theorem 5.1), and (2) explicitly represented polynomials have roughly the same power as extended straight-line programs when it comes to sets of fixed point (Lemma 5.1).

We start with the second part, for which we need a formal definition of the two variants of straight-line programs we mentioned. A straight-line program (SLP) is a sequence of assignments of the form S _i : = c,c∈{−1,−1/2,0,1/2,1}, S _i : = x _j ,i∈[ℓ],j∈[n] or S _i : = S _j ∘S _k , where 1≤j,k < i ≤ ℓ and ∘∈{+,−,∗}; ℓ is the length of the program.⁶ We can think of the straight-line program as a succinct way of describing a multivariate polynomial in variables x _j ,j∈[n], and we will sometimes write S _i (x) if we want to emphasize the dependence of S _i on the input variables x. A straight-line program for a function f=(f _i ) _i∈[m]:U→V, where $U \subseteq \mathbb {R}^{n}$, $V \subseteq \mathbb {R}^{m}$, is a straight-line program in which the first n assignments are S _i : = x _i , and the last m assignments calculate f _i (x ₁,…,x _n ) so that S _{ℓ−m + i} (x ₁,…,x _n ) = f _i (x ₁,…,x _n ), for i∈[m]. In an extended straight-line program (ESLP) we also allow operations /, max, min, and $\sqrt [k]{\cdot }$. (The definition in this case implies that for inputs in U no division by zero or even roots of negative numbers occur.)

The following lemma shows that ESLPs have no edge on explicitly represented polynomials with respect to capturing sets of fixed points: for each ESLP there is such a polynomial family that has essentially the same set of fixed points. We write F _f for the set of fixed points of a function f in its domain, and use 1 and 0 for the vector consisting of all ones or zeros (of appropriate dimension).

Lemma 5.1

If f:B _n (0,1)→B _n (0,1) is a function given by an ESLP, then we can construct in polynomial time a polynomial family $g: B_{n^{\prime }}(0,1) \rightarrow B_{n^{\prime }}(0,1)$ , n ^′ ≥n, so that F _f ∪{1}=π _n (F _g ), where $\pi _{n} : \mathbb {R}^{n^{\prime }} \rightarrow \mathbb {R}^{n}$ projects a vector on its first n coordinates. Moreover, we can ensure that $F_{f} \cap B_{n}(0,1/2) = \pi _{n}(F_{g} \cap B_{n^{\prime }}(0,1/2))$.

Remark 5.1

Two comments about the lemma: (i) There is nothing special about adding 1 as a fixed point when going from f to g, the construction we will use could be adapted to add any point in $[-1,1]^{n^{\prime }}$ describable by a polynomial. So one way to eliminate that point is by making this added fixed point a fixed point of f, however that would require the ability to find some (any) fixed point of f and that we will probably not be able to do in polynomial time: Papadimitriou showed that this problem is PPAD-complete [26]. It seems possible that there is a different construction which obviates the need to add an extra point as fixed point. One way to approach the problem would be to start with the stronger assumption that there is an SLP computing f. (i i) As it is, Lemma 5.1 tells us that finding an arbitrary fixed point of a function f:B _n (0,1)→B _n (0,1) specified by an ESLP can be reduced to finding at least two (arbitrary) fixed points of a polynomial family $g : B_{n^{\prime }}(0,1) \rightarrow B_{n^{\prime }}(0,1)$.

Proof Proof of Lemma 5.1

Let (S _i ) _i∈[ℓ] be the ESLP computing f. The first n instructions have the form S _i : = x _i , i∈[n], and the last n variables, S _ℓ−n+1,…,S _ℓ contain the outputs. We can assume that divisions are of the form S _i :=1/S _k ; moreover, since max{x,y}=(x + y+|x−y|)/2, min{x,y} = x + y− max{x,y} and $|x| = \sqrt {x^{2}}$, we can assume that the ESLP does not contain max or min (Etessami and Yannakakis use the same trick in [13]). Finally, we replace any instruction $S_{i} := \sqrt [k]{S_{j}}$ for even k with two instructions: $A := \sqrt [2k]{S_{j}}$, S _i : = A∗A; here A is a new variable of the ESLP we insert just before S _i (and which is only used to calculate S _i ). This modified ESLP will calculate S _i (and thus the rest of the program) correctly as the positive kth root of S _j , independently of whether $A = \sqrt [2k]{S_{j}}$ evaluates to the positive or negative 2k-th root of S _j .

We can consider each S _i as a function S _i (x ₁,…,x _n ) from $\mathbb {R}^{n}$ to $\mathbb {R}$; we know that every S _i is well-defined (no divisions by zero or even roots of negative arguments), but while the S _i calculating the output are restricted to values in [−1,1], the intermediate values can be large; however, since the input set is compact, there is an M so that S _i (x ₁,…,x _n )≤M/2 for all i∈[ℓ] and (x ₁,…,x _n )∈[−1,1]ⁿ. Consider ${\mathcal S} := \{(S_{1}(x), \ldots , S_{\ell }(x)): x \in [-1,1]^{n}\}$. Then ${\mathcal S}$ is a semi-algebraic set (all instructions can be rewritten as polynomial (in)equalities, e.g. $S_{i} := \sqrt [2k]{S_{j}}$ becomes $S_{i} \geq 0 \wedge S_{i}^{2k} - S_{j} = 0$ and $S_{i} := \sqrt [2k+1]{S_{j}}$ becomes $S_{i}^{2k+1} - S_{j} = 0$); hence, by Corollary 3.3, we can choose $M = 2^{2^{\log (c \ell ) \rceil + 5}}$ (for some c>0 which bounds the number of symbols needed to express a straight-line instruction).

The polynomial family g will have n ^′=3n+2ℓ+1 + m scalar variables grouped as x=(x ₁,…,x _n ), y=(y ₀,y ₁,…,y _ℓ ), $y^{\prime } = (y^{\prime }_{1}, \ldots , y^{\prime }_{\ell })$, z=(z ₁,…,z _n ), $z^{\prime } = (z^{\prime }_{1}, \ldots , z^{\prime }_{n})$, and u ^′=(u ₁,…,u _m ), where m=⌈log(c ℓ)⌉+5. For a fixed point g(x,y,y ^′,z,z ^′,u)=(x,y,y ^′,z,z ^′,u) we will ensure that

• $u_{i} = 2^{-2^{i}}$ for i∈[m],

• $y^{\prime }_{i} = 0$, and y _i = S _i /M for i∈[ℓ],

• $z^{\prime }_{i} = 0$, and z _i = S _{ℓ−n + i} for i∈[n],

unless y ₀=1, in which case we guarantee that x = 1. This means that (as long as y ₀≠1), u _m =1/M, the y _i simulate the calculations of the straight-line program scaled by the factor 1/M, and the z _i contain the actual output f(x). To simplify the presentation, we label the components of g by their variables, so we write $g_{x_{i}}$ or $g_{u_{j}}$ rather than using a uniform integer labeling g _i .

We start by defining $g_{x_{i}}$, $g_{z_{i}}$, $g_{z^{\prime }_{i}}$, and $g_{u_{i}}$. Let p(x):=1−(x−(1/4))²∗(1/4) and q(x): = x ²∗(1/16), where (1/4) is short for 1/2∗1/2 and similarly for (1/16).

• $g_{x_{i}} = z_{i}$ for i∈[n],

• $g_{z_{i}} = p(y_{0}) * z_{i} + 1-p(y_{0})$ for i∈[n],

• $g_{z^{\prime }_{i}} = q(y_{\ell -n+i} - z_{i} * u_{m})$ for i∈[n],

• $g_{u_{1}} = 1/2$, and $g_{u_{i+1}} = {u_{i}^{2}}$ for i∈[m−1].

Based on the instructions in the ESLP for f we construct the polynomials $g_{y^{\prime }_{i}}$ for i∈[ℓ]:

$$\begin{array}{@{}rcl@{}} S_{i} := c & \rightarrow & g_{y^{\prime}_{i}} := q(y_{i} - c*u_{m}) \\ S_{i} := x_{j} & \rightarrow & g_{y^{\prime}_{i}} := q(y_{i} - x_{j}*u_{m}) \\ S_{i} := S_{j} + S_{k} & \rightarrow & g_{y^{\prime}_{i}} := q(y_{i}-(y_{j}+y_{k})) \\ S_{i} := S_{j} * S_{k} & \rightarrow & g_{y^{\prime}_{i}} := q(y_{i}*u_{m}-(y_{j}*y_{k})) \\ S_{i} := 1/S_{j} & \rightarrow & g_{y^{\prime}_{i}} := q(y_{i}*y_{j}-1*{u_{m}^{2}}) \\ S_{i} := \sqrt[k]{S_{j}} & \rightarrow & g_{y^{\prime}_{i}} := q({y_{i}^{k}}-y_{j}*u_{m}^{k-1}) . \end{array} $$

Finally, let

• $g_{y_{0}} = 1- (1-y_{0}) * \left (1-{\sum }_{i \in [\ell ]} ((y^{\prime }_{i})^{2} + (z^{\prime }_{i})^{2})*(1/2)^{\lceil \log 2\ell \rceil } \right )$, and

• $g_{y_{i}} = y_{i}$, for i∈[ℓ].

This completes the definition of g which clearly is a polynomial family represented explicitly (the terms in $g_{y_{0}}$ can be multiplied out easily). We need to show that g also is a function from [−1,1]^{3n + ℓ+1 + m} to [−1,1]^{3n + ℓ+1 + m}. This is obvious for $g_{x_{i}}$, $g_{y_{i}}$, and $g_{u_{i}}$. Note that $g_{y^{\prime }_{i}}$ and $g_{z^{\prime }_{i}}$ take on values in [0,1] by choice of q: the terms to which q is applied all lie in the range [−3,3], since y _i , x _j , z _k , and u _m all lie in [−1,1], so by applying q we obtain numbers in [0,1]. Finally, $g_{z_{i}} \in [-1,1]$, since $g_{z_{i}} = p(y_{0}) * z_{i} + 1-p(y_{0}) \leq p(y_{0}) + 1 - p(y_{0}) = 1$ and $g_{z_{i}} \geq 1-2p(y_{0}) \geq -1$, and $g_{y_{0}} \in [-1, 1]$, since $0 \leq {\sum }_{i \in [\ell ]} (y^{\prime }_{i})^{2} + (z^{\prime }_{i})^{2} \leq 2\ell \leq 2^{\lceil \log 2\ell \rceil }$.

We next show that π _n (F _g )⊆F _f ∪{1}. To that end, let (x,y,y ^′,z,z ^′,u) be an arbitrary fixed point of g, that is, g(x,y,y ^′,z,z ^′,u)=(x,y,y ^′,z,z ^′,u). From the definition of $g_{u_{i}}$, for i∈[m], we conclude that u _m =1/M.

If y ₀=1, then p(y ₀)<1. Since $z_{i} = g_{z_{i}} = p(y_{0}) * z_{i} + 1-p(y_{0})$, we have z _i (1−p(y ₀))=1−p(y ₀) and thus z _i =1 for i∈[n]; but then $x_{i} = g_{x_{i}} = z_{i} = 1$ for i∈[n], so x = 1.

If, on the other hand, y ₀≠1, then because of $y_{0} = g_{y_{0}} = 1- (1-y_{0}) * (1-({\sum }_{i \in [\ell ]} (y^{\prime }_{i})^{2} + (z^{\prime }_{i})^{2})*(1/2)^{\lceil \log 2\ell \rceil })$ we have $1-y_{0}= (1-y_{0}) * (1-({\sum }_{i \in [\ell ]} (y^{\prime }_{i})^{2} + (z^{\prime }_{i})^{2})*(1/2)^{\lceil \log 2\ell \rceil })$ and thus ${\sum }_{i \in [\ell ]} (y^{\prime }_{i})^{2} + (z^{\prime }_{i})^{2} = 0$ which implies $y^{\prime }_{i} = 0$ for all i∈[ℓ] and $z^{\prime }_{i} = 0$ for all i∈[n]. To argue that y _i = S _i /M, we distinguish cases based on the instruction defining S _i ; we use that q(x)=0 implies that x=0.

• S _i : = c: since $y^{\prime }_{i} = 0$ we get that q(y _i −c∗u _m )=0 and thus y _i = c∗u _m = c/M,

• S _i : = x _j : since $y^{\prime }_{i} = 0$ we get that q(y _i −x _j ∗u _m )=0 and thus y _i = x _j ∗u _m = x _j /M, or, in other words, M∗y _i = x _j ,

• S _i : = S _j + S _k ; we get y _i = y _j + y _k ,

• S _i : = S _j ∗S _k we get y _i /M=(y _j ∗y _k ), so M∗y _i =(M∗y _j )∗(M∗y _k ),

• S _i :=1/S _j ; we get y _i ∗y _j =1/M ², so M∗y _i =1/(M∗y _j ),

• $S_{i} := \sqrt [k]{S_{j}}$; we get ${y_{i}^{k}}=y_{j}/M^{k-1}$, so (M∗y _i )^k = M∗y _j (recall that if k is even we have ensured that S _j ≥0).

This is enough to show inductively that y _i = S _i /M in the first five cases and |y _i |=|S _i |/M in the last case (which is sufficient as we saw earlier). A similar argument about the $g_{z^{\prime }_{i}}$ with $z^{\prime }_{i} = 0$ shows that y _{ℓ−n + i} = z _i /M, so z _i = M∗y _{ℓ−n + i} = S _{ℓ−n + i} ; now, since $x_{i} = g_{x_{i}} = z_{i}$, this shows that the fixed point of g, if projected on its first n coordinates (x ₁,…,x _n ), is a fixed point of f. This completes the proof that π _n (F _g )⊆F _f ∪{1} which, in turn, implies that $\pi _{n}(F_{g} \cap B_{n^{\prime }}(0,1/2)) \subseteq \pi _{n}(F_{g}) \cap B_{n}(0,1/2) \subseteq F_{f} \cap B_{n}(0,1/2)$, where n ^′=3n+2ℓ+1 + m.

To see that F _f ∪{1}⊆π _n (F _g ), let x be a fixed point of f, that is, f(x) = x. We set $u_{i} = 2^{-2^{i}}$ satisfying $g_{u_{i}} = u_{i}$. Let y ₀=1/4, so that p(y ₀)=1, and thus $g_{z_{i}} = p(y_{0}) * z_{i} + 1-p(y_{0}) = z_{i}$ for any choice of z _i ∈[−1,1]. Then letting $y^{\prime }_{i} = 0$, and y _i = S _i (x)/M for i∈[ℓ], and $z^{\prime }_{i} = 0$, and z _i = S _{ℓ−n + i} (x) for i∈[n], satisfies the remaining clauses of g, showing that (x,y,y ^′,z,z ^′,u) is a fixed point of g and F _f ⊆π _n (F _g ). Moreover, for the same values of y, y ^′, z ^′, and u, we see that (1,y,y ^′,1,z ^′,u) is a fixed point of g as well (recall that there is no restriction on the z _i , since g(z _i ) = z _i for the particular value of y ₀ we chose, and x = z is all that is required to satisfy the $g_{x_{i}}$), showing that 1∈π _n (F _g ).

We note that something slightly stronger than F _f ⊆π _n (F _g ) is true, since we can bound by 1/2 all the intermediate variables for the fixed point (x,y,y ^′,z,z ^′,u) of g corresponding to the fixed point x of f: We have y ₀=1/4, |y _i |=|S _i (x)/M|≤1/2 (by choice of M), |u _i |≤1/2, $y^{\prime }_{i} = 0$, and $z^{\prime }_{i} = 0$. So (x,y,y ^′,z,z ^′,u)∈F _f ×B _2ℓ+1(0,1/2)×F _f ×B _{n + m} (0,1/2). In particular, $F_{f} \cap B_{n}(0,1/2) \subseteq \pi _{n}(F_{g} \cap B_{n^{\prime }}(0,1/2)$, where n ^′=3n+2ℓ+1 + m.

In summary, π _n (F _g ) = F _f ∪{1}, and $F_{f} \cap B_{n}(0,1/2) = \pi _{n}(F_{g} \cap B_{n^{\prime }}(0,1/2))$, concluding the proof of the lemma. □

With Lemma 5.1 it is now easy to show that BROUWER is $\exists \mathbb {R}$-hard.

Theorem 5.1

Deciding BROUWER is $\exists \mathbb {R}$ -complete, even for x=0 and r=1/2.

The theorem remains true for any other appropriate choice of x and r. For fixed dimension, e.g. n=1 or n=2, BROUWER can be decided in P using quantifier elimination for the fixed number of quantifiers.

Proof

The problem is easily seen to lie in $\exists \mathbb {R}$ (this remains true even if f is specified by an SLP or an ESLP). We saw earlier that deciding whether a family of multivariate polynomials $f = (f_{i})_{i \in [n]} : \mathbb {R}^{n} \rightarrow \mathbb {R}^{n}$ has a fixed point is hard for $\exists \mathbb {R}$; since these polynomials are given explicitly, it is easy to construct an SLP S computing f. By Corollary 3.1 if f has a fixed point, there has to be a fixed point at distance less than $R/2 = 2^{(c\ell )^{8n}}$ from 0, where ℓ is the length of S, and c is a fixed constant. Now f maps B _n (0,R) to B _n (0,R ^′), where $R^{\prime } = \lceil R^{2^{\ell }} \rceil \leq \lceil 2^{2^{c^{\prime }\ell n}} \rceil$ (each coordinate can be at most squared in each of the at most ℓ steps of the computation; c ^′ only depends on c, so it is a fixed constant). Let g be the continuous map that is the identity on B _n (0,R/2) and bijectively maps B _n (0,R ^′)−B _n (0,R/2) to B _n (0,R)−B _n (0,R/2) defined component-wise by:

$$g_{i}(x) = \left\{ \begin{array}{ll} x_{i} & \text{if \(x_{i} \in B_{1}(0,R/2)\)} \\ \text{sgn}(x_{i}) \frac{R}{2} \left( \frac{|x_{i}| - (R/2)}{R^{\prime} - R/2} + 1 \right) & \text{if \(x_{i} \in B_{1}(0,R^{\prime})-B_{1}(0,R/2)\)} \end{array} \right. $$

for i∈[n], where sgn(x) is the sign function. Then g∘f maps B _n (0,R) to B _n (0,R); moreover, any fixed point of f in B _n (0,R/2) is still a fixed point of g∘f in B _n (0,R/2) and vice versa. Finally, let h be a scaling by R, that is h is a continuous bijection between B _n (0,R) and B _n (0,1). Thus h∘g∘f∘h ⁻¹:B _n (0,1)→B _n (0,1) has a fixed point in B _n (0,1/2) if and only if f has a fixed point (in $\mathbb {R}^{n}$).

Now, there will not, in general, be an SLP computing h∘g∘f∘h ⁻¹ since such an SLP would require division and case distinction; however, it is easy to see that there is an ESLP: this is clear for h and most of g; the only interesting question is how to perform the case distinction, but that can be done using max and min:

$$\begin{array}{@{}rcl@{}} g_{i}(x) &=& \max(0,\min(x_{i}, R/2) + \frac{R}{2} \max(0, \frac{x_{i} - R/2}{R^{\prime}-R/2}))\\ &&\qquad\qquad\qquad- \max(0,\min(-x_{i}, R/2) + \frac{R}{2} \max(0, \frac{-x_{i} - R/2}{R^{\prime}-R/2})) . \end{array} $$

Finally, ESLPs are closed under composition of functions, so we can conclude that there is an ESLP for h∘g∘f∘h ⁻¹ and thus, by Lemma 5.1 an explicitly represented polynomial family $f^{\prime }: B_{n^{\prime }}(0,1) \rightarrow B_{n^{\prime }}(0,1)$ so that $F_{h \circ g \circ f \circ h^{-1}} \cup \{\mathbf {1}\}= \pi _{n}(F_{f^{\prime }})$. Moreover, the lemma allows us to conclude that

$F_{h \circ g \circ f \circ h^{-1}} \cap B_{n}(0,1/2) = \pi _{n}(F_{f^{\prime }} \cap B_{n^{\prime }}(0,1/2))$.

Now f has a fixed point if and only if h∘g∘f∘h ⁻¹ has a fixed point in B _n (0,1/2) if and only if f ^′ has a fixed point in $B_{n^{\prime }}(0,1/2)$, which is the BROUWERs problem for the explicitly represented polynomial family f ^′. □

5.2 The Nash Equilibrium

Etessami and Yannakakis [13] studied in depth the search versions of fixed-point problems and Nash equilibria⁷: Suppose we are given a function f:B _n (0,1)→B _n (0,1) via an ESLP. How hard is it to find some (any) fixed point of f? This, of course, is a problem over real numbers, but one can turn it into a discrete problem as follows. For any input $r \in \mathbb {Q}^{n}$ we are allowed to ask questions of the type xΘr, where Θ is one of {≤,≥,<,>}ⁿ, a vector of comparison operators. If xΘr for all fixed points x of f the answer has to be “yes”, if xΘr is false for all fixed points of f the answer has to be “no”; otherwise, the answer can be either “yes” or “no”. Etessami and Yannakakis call this the decision problem (in their terminology, BROUWER is an existence problem, not a decision problem). The class of all such fixed-point decision problems they call FIXP _d . FIXP _d is rather robust, for example it is not affected by changing the domain of the function (to a cube, or a sphere, say). Etessami and Yannakakis [13, Theorem 4.7] also show that FIXP _d remains the same if ESLPs are restricted to {+,∗,max}.⁸

Moreover, FIXP _d has natural complete problems, including, among several others, the decision (in Etessami and Yannakakis’s terminology) versions of BROUWER and the Nash equilibrium problem for 3 players. Clearly, FIXP $_{d} \subseteq \exists \mathbb {R}$, and Etessami and Yannakakis show that PSLP reduces to any FIXP _d -complete problem, where PSLP is the problem of deciding whether a given SLP computes a positive number; currently this is the best known lower bound on FIXP _d (in turn, the best-known upper bound on PSLP is the counting hierarchy, due to a result by Allender, Bürgisser, Kjeldgaard-Pedersen, and Miltersen [1]). Etessami and Yannakakis point out that it is unlikely that any FIXP _d -problem is NP-hard, since in that case it is also coNP-hard, which would imply coNP $\subseteq \exists \mathbb {R}$, which is not impossible, but seems counterintuitive. Similarly, FIXP $_{d} = \exists \mathbb {R}$ would imply that $\exists \mathbb {R}$ is closed under complement, which again appears unlikely.

Here we consider decision versions of the Nash equilibrium problem in which we ask whether there is a Nash equilibrium in a given ball B _n (x,r). Etessami and Yannakakis’s core result works in this setting as well; we summarize it in the following lemma:

Lemma 5.2 (Etessami, Yannakakis [13, Claim 2 in Theorem 4.3])

Given a function f:B _n (0,1)→B _n (0,1) specified by an SLP of length ℓ, one can construct in polynomial time a 3-player game G and compute an integer N=O(ℓ) so that

• if x ^∗ is a fixed point of f then there is a Nash equilibrium z=(z ₁ ,z ₂ ,z ₃ ) of Γ so that z ₁ [1:n]=x ^∗ /N,

• if z=(z ₁ ,z ₂ ,z ₃ ) is a Nash equilibrium of Γ, then x ^∗ =Nz ₁ [1:n] is a fixed point of f.

By Theorem 5.1, BROUWER is $\exists \mathbb {R}$-hard, and Lemma 5.2 shows that there is a reduction from BROUWER to the Nash equilibrium problem, so the following corollary is immediate now.

Corollary 5.1

Deciding whether a 3-player game Γ has a Nash equilibrium in B _n (x,r) for $x \in \mathbb {Q}^{n}$ , $r \in \mathbb {Q}$ is $\exists \mathbb {R}$ -complete even for x=0.

In the corollary, we can take r=1/(2N), where N is as in Lemma 5.2. More precisely, given an instance of BROUWER with r=1/2 we use Lemma 5.2 to construct a 3-player game G and N and then use G and r=1/(2N) as an instance of the “Nash equilibrium in a ball” problem.

Remark 5.2

Datta showed the universality of 3-player totally mixed Nash equilibria [11]; algebraically this is a stronger result, since it shows that arbitrary semi-algebraic sets can be encoded as Nash equilibria; however, the reduction is not polynomial time, since some players in her game use Ω(d ⁿ) pure strategies, where d is the highest power of any variable in the polynomial equations encoding the semi-algebraic sets, see [11, Theorem 2]. It may be an interesting open problem whether Datta’s universality theorem can be improved to an efficient, that is, polynomial-time, reduction.

Etessami and Yannakakis have also given a reduction from BROUWER (with max) to the exchange equilibrium problem (see [13, Proposition 4.4] for details); starting with our more restrictive version of BROUWER, we can conclude that the problem remains hard if the ESLP is restricted further.

Corollary 5.2

The exchange equilibrium problem with an excess demand function given by an ESLP is $\exists \mathbb {R}$ -complete. Indeed, this remains true if the ESLP is restricted to division (that is, no roots, max or min operations are allowed).

Appendix A: Proof of Corollary 3.4

Let $S = \{x \in \mathbb {R}^{n}: \varphi (x)\}$ be the semi-algebraic set defined by φ of complexity at most L. If S = ∅, there is nothing to show, so we can assume that S≠∅. By Lemma 3.1 there is a conjunction $\psi = \bigwedge _{i=1}^{\ell } s_{i} \triangle _{i} t_{i}$ with △ _i ∈{<,=} so that $S^{\prime } = \{x \in \mathbb {R}^{n}: \psi (x)\}$ is a non-empty subset of S and |ψ|≤|φ|≤L. In particular, ℓ < L. Now $S^{\prime } = \{x \in \mathbb {R}^{n}: s_{i} - t_{i} \triangle _{i} 0\}$. Let f _i : = s _i −t _i , and s = ℓ. Then s < L, each f _i has degree d at most L−2 (we need two symbols for △ _i and 0), and the bitlength of each coefficient of f _i is bounded by L−1, so τ < L (these are wildly generous bounds). Hence, we can apply Theorem 3.1 to conclude that S ^′, and therefore S contains a point at distance at most R from the origin if it is non-empty. We are left with the estimate of R. Let us first simplify the expression for R:

$$\begin{array}{@{}rcl@{}} R & \leq & ((4DN^{2}) 2^{2N(\tau^{\prime}+b(2N)+b(2DN+1))})^{1/2} \\ & \leq & 2DN 2^{N(\tau^{\prime}+b(2N)+b(2DN+1))} \\ & \leq & 2^{b(N) + b(2D) + N(\tau^{\prime}+b(2N)+b(2DN+1))}. \end{array} $$

We know that d ^′<2L (using L≥4); then D ≤ n d ^′<2n L, and 2D+1≤4n L. With this b(2D+1)≤b(4n L)≤3+ log(n L)≤n L+3 (we’re using b(x)≤ log(x)+1). Now N≤(d ^′)ⁿ≤(2L)ⁿ, so b(N) = b((2L)ⁿ)≤1 + n log(2L)≤n L+1 (for L≥4), and b(2N)≤n L+2. We can now evaluate the τ-values: τ ₀≤2L+(n+1)b(L) + b(4L)≤2L+(n+2) logL+(n+4)≤5n L (for L≥4); with that, τ ₁≤D(τ ₀+4b(2D+1) + b(N))≤2n L(5n L+4(n L+3)+(n L+1))≤27n ² L ², and τ ₂≤τ ₁+2n(b(N) + b(n))≤τ ₁+2n ² L ²≤29n ² L ², τ ^′≤N(τ ₂+(n L+1)+2(n L+3)+1)≤(2L)ⁿ(31n ² L ²+8)≤(2L)ⁿ32n ² L ²≤32n ² L ³ⁿ.This allows us to evaluate the expression τ ^′ + b(2N) + b(2D N+1)≤τ ^′+1+2b(N) + b(2D+1)≤32n ² L ³ⁿ+3n L+5≤35n ² L ³ⁿ. Finally,

$$\begin{array}{@{}rcl@{}} R & \leq & 2^{b(N) + b(2D) + N(\tau^{\prime}+b(2N)+b(2DN+1))} \\ & \leq & 2^{(nL+1) + (nL+3) + N(35n^{2}L^{3n})} \\ & \leq & 2^{(2nL+4) + (2L)^{n} (35n^{2}L^{3n})} \\ & \leq & 2^{35n^{2} L^{5n}} \\ & \leq & 2^{L^{8n}}, \end{array} $$

which is what we had to show.