# On Classifying Continuous Constraint Satisfaction problems

Tillmann Miltzow  Computer Science Department, Utrecht University,
<EMAIL_ADDRESS>Reinier F. Schmiermann  Mathematics Department,
Utrecht University<EMAIL_ADDRESS>
###### Abstract

A continuous constraint satisfaction problem (CCSP) is a constraint
satisfaction problem (CSP) with an interval domain $U\subset\mathbb{R}$. We
engage in a systematic study to classify CCSPs that are complete of the
Existential Theory of the Reals, i.e., $\exists\mathbb{R}$-complete. To define
this class, we first consider the problem ETR, which also stands for
Existential Theory of the Reals. In an instance of this problem we are given
some sentence of the form $\exists
x_{1},\ldots,x_{n}\in\mathbb{R}:\Phi(x_{1},\ldots,x_{n})$, where $\Phi$ is a
well-formed quantifier-free formula consisting of the symbols
$\\{0,1,x_{1},\ldots,x_{n},+,\cdot,\geq,>,\wedge,\vee,\neg\\}$, the goal is to
check whether this sentence is true. Now the class $\exists\mathbb{R}$ is the
family of all problems that admit a polynomial-time many-one reduction to ETR.
It is known that
$\textrm{NP}\subseteq\exists\mathbb{R}\subseteq\textrm{PSPACE}$.

We restrict our attention on CCSPs with addition constraints ($x+y=z$) and
some other mild technical condition. Previously, it was shown that
multiplication constraints ($x\cdot y=z$), squaring constraints ($x^{2}=y$),
or inversion constraints ($x\cdot y=1$) are sufficient to establish
$\exists\mathbb{R}$-completeness. We extend this in the strongest possible
sense for equality constraints as follows. We show that CCSPs (with addition
constraints and some other mild technical condition) that have any one well-
behaved curved equality constraint ($f(x,y)=0$) are
$\exists\mathbb{R}$-complete. We further extend our results to inequality
constraints. We show that any well-behaved convexly curved and any well-
behaved concavely curved inequality constraint ($f(x,y)\geq 0$ and $g(x,y)\geq
0$) imply $\exists\mathbb{R}$-completeness on the class of such CCSPs.

Here, we call a function $f\colon U^{2}\to\mathbb{R}$ well-behaved if it is a
$C^{2}$-function, $f(0,0)=0$, all its partial derivatives $f_{x},f_{y},f$ are
rational in $(0,0)$, $f_{x}(0,0)\neq 0$ or $f_{y}(0,0)\neq 0$, and it can be
computed on a real RAM. Furthermore we call $f$ curved if the curvature of the
curve given by $f(x,y)=0$ is nonzero, at the origin. In this case we call $f$
either convexly curved if the curvature is negative, or concavely curved if it
is positive.

We apply our findings to geometric packing and answer an open question by
Abrahamsen et al. [5, FOCS 2020]. Namely, we establish
$\exists\mathbb{R}$-completeness of packing convex pieces into a square
container under rotations and translations.

Figure 1: Real examples of packing a leather hide (left) and a piece of fabric
(right), kindly provided by MIRISYS and produced by their software for
automatic nesting, https://www.mirisys.com/.

##  1 Introduction

In geometric packing, we are given a set of two-dimensional pieces, a
container and a set of motions. The aim is to move the pieces into the
container without overlap, and while respecting the given motions. Recently,
Abrahamsen, Miltzow and Seiferth showed that many geometric packing problems
are $\exists\mathbb{R}$-complete (FOCS 2020) [5]. Despite the fact that the
arXiv version is roughly 100 pages long, the high-level approach follows the
same principle as many other hardness reductions. First, they showed that a
technical intermediate problem is hard and then they reduced from this
technical problem. In their case, a specific continuous constraint
satisfaction problem called ETR-INV serves as this intermediate
$\exists\mathbb{R}$-complete problem. Specifically, ETR-INV contains
essentially only addition constraints ($x+y=z$) and inversion constraints
($x\cdot y=1$). In the second step, they showed how to encode addition and
inversion using geometric objects. This enabled them to show in a unified
framework that various geometric packing problems are
$\exists\mathbb{R}$-complete, see Figure 2.

The inversion constraint is particularly handy as it was shown in various
other works that it is particularly easy to encode geometrically [31, 20, 21,
2]. Curiously, Abrahamsen, Miltzow and Seiferth left arguably the most
interesting case of packing convex polygonal objects into a square container
open. The missing puzzle piece seemed to be a gadget to encode the inversion
constraint for this case. They dedicate Section 8.4 on explaining the
difficulties to find such a gadget and give the following comment.

“Gadget wanted! Most interesting to us is whether there exists a gadget
encoding $x\cdot y\leq 1$, using a polygonal container, convex polygonal
pieces, and rotation. […] Despite much effort, we could not find such a
gadget.”

We take an alternative approach and engage in a systematic study of continuous
constraint satisfaction problems in their own respect. The aim is to fully
classify all continuous constraint satisfaction problems, by their
computational complexity. Polynomial time, NP-complete, and
$\exists\mathbb{R}$-complete are some apparent complexities, but as we will
see, they may not be the only ones that are relevant, see Section 1.4. Our
first theorem arises as a combination of a small adaption of the framework by
[5] and an application of our structural results.

######  Theorem 1.

Packing convex polygons into a square under rigid motions is
$\exists\mathbb{R}$-complete.

Interestingly, we employ our structural result only for one simple special
case. Still, we would not know how to prove that case without establishing the
theorem in its full generality. Before we explain our alternative approach, we
give a short introduction to constraint satisfaction problems and the
complexity class $\exists\mathbb{R}$. See Figure 2 for a comparison to
previous $\exists\mathbb{R}$-completeness results for geometric packing.

Figure 2: Various packing variants and their complexity status established in
[5]. The results with an asterisk are new and complete the picture for packing
variants that involve rotations. Image used with permission [5].

###  1.1 Constraint Satisfaction Problems

Constraint satisfaction problems (CSPs) are a wide class of computational
decision problems. In order to give a formal definition, we first introduce
several other terms.

######  Definition 2 (Signature).

A signature is a finite set of symbols together with arities
$\ell\in\mathbb{N}$. Note that each symbol has exactly one arity attached to
it. Often the signature distinguishes between function symbols and relational
symbols. We will only use relational symbols.

Note that a signature is also called template, constraint language, or
vocabulary in the literature.

######  Definition 3 (Structure).

A structure consists of a set $U$, called the domain, a signature $\tau$ and
an interpretation of each symbol. If $\alpha\in\tau$ is a symbol of arity
$\ell$, then the interpretation is a set $\alpha\subseteq U^{\ell}$.

To make this more tangible, consider the following example. We define the
domain as $U=\\{0,1\\}$, the symbol $+_{2}$ of arity $3$ and the symbol
$\mathbf{1}$ of arity $1$. We interpret $+_{2}$ as $\left\\{(x,y,z)\in
U^{3}\,\middle|\,x+y\equiv z\left(\mathrm{mod}\;2\right)\right\\}$, and
$\mathbf{1}$ as $\left\\{x\in U\,\middle|\,x=1\right\\}$. This defines a
structure $S_{1}=\langle U=\\{0,1\\},+_{2},\mathbf{1}\rangle$. Note that it is
common to use a symbol and its interpretation interchangeably. Specifically,
many symbols are used in the literature with their common interpretation,
e.g., $\leq$ is interpreted as $\left\\{(x,y)\in U\,\middle|\,x\leq
y\right\\}$ and $+$ is interpreted as $\left\\{(x,y,z)\in
U^{3}\,\middle|\,x+y=z\right\\}$. We refer to the symbols and interpretations
of a structure merely as constraints. We will usually denote these constraints
by the equation that they enforce. For example, we write $x^{2}=y$ for the
constraint $c=\left\\{(x,y)\in U^{2}\,\middle|\,x^{2}=y\right\\}$.

######  Definition 4 (Constraint satisfaction problem).

Given a structure $S=(U,\tau)$ we define a constraint formula
$\Phi:=\Phi(x_{1},\ldots,x_{n})$ to be a conjunction $c_{1}\wedge\ldots\wedge
c_{m}$ for $m\geq 0$, where each $c_{i}$ is of the form
$c(y_{1},\ldots,y_{\ell})$ for some $c\in\tau$ and variables
$y_{1},\ldots,y_{\ell}\in\\{x_{1},\ldots,x_{n}\\}$. We also define
$V(\Phi)\subseteq U^{n}$ as $V(\Phi):=\left\\{\mathbf{x}\in
U^{n}\,\middle|\,\Phi(\mathbf{x})\right\\}$. In the constraint satisfaction
problem (CSP) with structure $S$, we are given a constraint formula $\Phi$,
and are asked whether $V(\Phi)\neq\emptyset$.

Consider the constraint formula $\Phi=(x_{1}+x_{2}\equiv
x_{4}\left(\mathrm{mod}\;2\right))\land(x_{2}+x_{3}\equiv
x_{4}\left(\mathrm{mod}\;2\right))\land(x_{2}=1)$ gives an instance of a CSP
with structure $S_{1}$ as above. Note that $(0,1,0,1)\in V(\Phi)$. It can be
interesting whether the CSP with structure $S_{1}$ is polynomial time
solvable.

In this paper, we restrict ourselves to interval domains
$U\subseteq\mathbb{R}$ and denote them as continuous constraint satisfaction
problems (CCSPs).

Constraint satisfaction problems (CSPs) have a long history in algorithmic
studies [46, 14, 15, 51, 33, 22]. There are two application driven motivations
to study them. On the one hand, it is possible to easily encode many
fundamental algorithmic problems directly as a CSP. Then, given an efficient
algorithm for those types of CSPs, we have immediately also solved those other
algorithmic problems. On the other hand, if we can encode CSPs into
algorithmic problems, then then any hardness result for the CSP immediately
carries over to the algorithmic problem. Next to an application driven
motivation, it is fair to say that they deserve a study in their own right as
fundamental mathematical objects. CSPs are a very versatile language and often
allow for a complete classification by their computational complexity.
Specifically, the tractability conjecture states that every class of CSP with
a finite domain is either NP-complete or polynomial time solvable. Schaefer
showed the conjecture for domains of size two [46]. Recently Bulatov and Zhuk
could confirm the conjecture independently [15, 51] for any finite domain.
Note that one can also try to find a classification from the parametrized
complexity perspective [33] or the approximation counting perspective [22].

In this paper, we focus on CSPs with a interval domain $U\subset\mathbb{R}$
and we are interested in the class of CSPs that are
$\exists\mathbb{R}$-complete. We want to point out that there is also a large
body of research that deals with infinite domains [52, 50, 10, 12, 28]. Most
relevant for us is the work by Bodirsky, Jonsson and von Oertzen [11], who
also studied CSPs over the reals and showed that a host of them are NP-hard to
decide. Specifically, they defined a subset $S$ of $\mathbb{R}^{n}$ as
essentially convex if for all $a,b\in S$, the straight line segment intersects
the complement $\overline{S}$ of $S$ in finitely many points. They show that
CSPs that contain $x=1$, $x>0$, $x\leq y$, and at least one constraint that is
not essentially convex are NP-hard. However, their techniques do not imply
$\exists\mathbb{R}$-hardness. See also [13] for an overview of results for the
real domain.

###  1.2 Existential Theory of the Reals

The class of the existential theory of the reals $\exists\mathbb{R}$
(pronounced as ‘ER’) is a complexity class which has gained a lot of interest,
specifically within the computational geometry community. To define this
class, we first consider the problem ETR, which also stands for Existential
Theory of the Reals. In an instance of this problem we are given some sentence
of the form

$\exists x_{1},\ldots,x_{n}\in\mathbb{R}:\Phi(x_{1},\ldots,x_{n}),$

where $\Phi$ is a well-formed quantifier-free formula consisting of the
symbols $\\{0,1,x_{1},\ldots,x_{n},+,\cdot,\geq,>,\wedge,\vee,\neg\\}$, the
goal is to check whether this sentence is true. As an example of an ETR-
instance, we could take $\Phi=x\cdot y^{2}+x\geq 0\wedge\neg(y<2x)$. The goal
of this instance would be to determine whether there exist real numbers $x$
and $y$ satisfying this formula. Now the class $\exists\mathbb{R}$ is the
family of all problems that admit a polynomial-time many-one reduction to ETR.
It is known that

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

The first inclusion follows from the definition of $\exists\mathbb{R}$.
Showing the second inclusion was first done by Canny in his seminal paper
[16]. The CSP of the structure
$\mathbf{R}=\langle\mathbb{R},\cdot,+,\mathbf{1}\rangle$ is
$\exists\mathbb{R}$-complete [34]. The reason that $\exists\mathbb{R}$ is an
important complexity class is that a number of common problems in
computational geometry have been shown to be complete for this class.

#### Scope.

The main reason that the complexity class $\exists\mathbb{R}$ gained traction
in recent years is the increasing number of important algorithmic problems
that are $\exists\mathbb{R}$-complete. Marcus Schaefer established the current
name and pointed out first that several known NP-hardness reductions actually
implied $\exists\mathbb{R}$-completeness [41]. Note that some important
reductions that establish $\exists\mathbb{R}$-completeness were done before
the class was named.

Problems that have a continuous solution space and non-linear relation between
partial solutions are natural candidates to be $\exists\mathbb{R}$-complete.
Early examples are related to recognition of geometric structures: points in
the plane [36, 49], geometric linkages [42, 1], segment graphs [30, 34], unit
disk graphs [35, 29], ray intersection graphs [17], and point visibility
graphs [18]. In general, the complexity class is more established in the graph
drawing community [31, 20, 43, 23]. Yet, it is also relevant for studying
polytopes [40, 21]. There is a series of papers related to Nash-Equilibria [7,
45, 25, 8, 9]. Another line of research studies matrix factorization problems
[19, 47, 48, 44]. Other $\exists\mathbb{R}$-complete problems are the Art
Gallery Problem [2] and training neural networks [3].

#### Practical Implications.

It is maybe at first not entirely clear why we should care about
$\exists\mathbb{R}$-completeness, when we know for most of those problems that
they are NP-hard. The answer has different aspects. One reason is that we are
intrinsically interested in establishing the true complexity of important
algorithmic problems. Furthermore, $\exists\mathbb{R}$-completeness helps us
to understand better the difficulties encountered when designing algorithms
for those types of problems. While we have a myriad of techniques for NP-
complete problems, most of these techniques are of limited use when we
consider $\exists\mathbb{R}$-complete problems. The reason being that
$\exists\mathbb{R}$-complete problems have an infinite set of possible
solutions that are intertwined in a sophisticated way. Many researchers have
hoped to discretize the solution space, but success was limited [27, 34]. The
complexity class $\exists\mathbb{R}$ connects all of those different problems
and tells us that we can either discretize all of them or none of them. To
illustrate our lack of sufficient worst-case methods, note that we do not know
the smallest square container to pack eleven unit squares, see Figure 3.

Figure 3: Left: Five unit squares into a minimum square container. Right: This
is the best known packing of eleven unit squares into a square container [26].

#### Technique.

In order to show $\exists\mathbb{R}$-completeness, usually two steps are
involved. The first step is a reduction to a technical variant of ETR. The
second step is a reduction from that variant to the problem at hand. Those ETR
variants are typically CCSP’s with only very limited types of constraints. It
is common to have an addition constraint ($x+y=z$), and a non-linear
constraint, like one of the following:

$z=x\cdot y,\quad z=x^{2},\quad 1=x\cdot y.$

To find the right non-linear constraint is crucial for the second step, as it
is often very difficult to encode non-linear constraints in geometric
problems. Previous proof techniques relied on expressing multiplication
indirectly using other operations. To be precise, we say that a constraint $c$
of arity $\ell$ has a positive primitive definition in structure $S$, if there
is a constraint formula $\Phi$ in $S$ such that $c(y_{1},\ldots,y_{\ell})$ if
and only if $\exists
x_{1},\ldots,x_{k}:\Phi(y_{1},\ldots,y_{\ell},x_{1},\ldots,x_{k})$. In that
case, $\Phi$ is called a positive primitive formula, or just pp-formula. For
instance, we can express multiplication using squaring and addition as
follows:

$x\cdot y=\left(\frac{x+y}{2}\right)^{2}-\left(\frac{x-y}{2}\right)^{2}.$

This translates into a pp-formula as follows. $\exists
A_{0},A_{1},A_{2},B_{0},B_{1},B_{2}:$

$\begin{array}[]{rcl}A_{0}&=&x+y,\\\ A_{0}&=&A_{1}+A_{1},\\\
A_{2}&=&A_{1}^{2},\\\ \end{array}$ $\begin{array}[]{rcl}x&=&y+B_{0},\\\
B_{0}&=&B_{1}+B_{1},\\\ B_{2}&=&B_{1}^{2},\end{array}$ $A_{2}=B_{2}+z.$

Given a pp-formula, we can reduce a CSP with constraint $c$ to a CSP with a
different signature. Here, we replaced the ternary constraint $x\cdot y=z$ by
the binary constraint $x^{2}=y$.

Furthermore, there are often some range constraints of the form $x>0$,
$x\in[1/2,2]$ or even $x\in[-\delta,\delta]$, for some $\delta=O(n^{-c})$,
where $n$ is the number of variables. The above reduction becomes even more
involved as the range constraints need to hold for every intermediate variable
as well. They are important as we may only be able to encode variables in a
certain limited range. Finally, it may be useful to know some structural
properties of the variable constraint graph, like planarity. Those structural
properties can often be imposed solely by self-reductions and repeated usage
of the addition constraint.

Overall, those techniques have their limitations. As the reductions rely on an
explicit way to express one non-linear constraint by another non-linear
constraint and addition, we have to find those identities. To illustrate this,
we encourage the reader to find a way to express multiplication using
$x^{2}+y^{2}=1$ and linear constraints. (See Appendix A for the solution.)
This gets more tricky when dealing with inequality constraints. For instance,
it is not clear how to express multiplication with $x\cdot y\geq 1$ and
$x^{2}+y^{2}\geq 1$. We offer $10$ euro to the first person, who is able to
find a pp-formula to do so. Note that our theorems imply that those two
inequalities together with linear constraints are enough to establish
$\exists\mathbb{R}$-completeness, but we do not describe a pp-formula. We do
not know whether the concave constraint $x\cdot y\leq 1$ is sufficient to
establish $\exists\mathbb{R}$-completeness. At last, translating those
identities into a reduction that respects the range constraints for every
variable becomes very tedious and lengthy. Furthermore, it only establishes
$\exists\mathbb{R}$-completeness for those specific constraints. See
Abrahamsen and Miltzow [4] for some of those reductions.

We overcome this limitation by developing a new technique that establishes
$\exists\mathbb{R}$-completeness for virtually any one non-linear equality
constraint. We extend our results and show that any one convex and any one
concave inequality constraint are also sufficient to establish
$\exists\mathbb{R}$-completeness. See Section 1.3 for a formal description of
our results and Section 1.5 for an overview of our techniques.

###  1.3 Results

We focus on the special case with essentially only one addition constraint and
any one non-linear constraint. While this may seem like a strong limitation,
note that addition constraints are commonly easy to encode. In most
applications, the non-linear constraint is the crucial one.

######  Definition 5 (Curved equality problem (CE)).

We assume that we are given $\delta>0$, a domain $[-\delta,\delta]\subseteq U$
and a function $f\colon U^{2}\rightarrow\mathbb{R}$. Then we define the
signature $C(f,\delta)$ as

$C(f,\delta)=\\{x+y=z,\;f(x,y)=0,\;x\geq 0,\;x=\delta\\}.$

The CE problem is the CCSP given by $C(f,\delta)$. Furthermore, we are
promised that $V(\Phi)\subseteq[-\delta,\delta]^{n}$.

By slight abuse of notation, we also allow that $\delta$ is given as part of
the input. Note that although the problem is called curved equality problem,
we make no assumptions on $f$ as part of the definition. We do this
explicitly, as there are various technical ways to formulate those
assumptions. Abrahamsen, Adamaszek and Miltzow [2, 4] essentially showed that
CE is $\exists\mathbb{R}$-complete for $f=(x-1)(y-1)-1$. Here, we generalize
this to a wider set of functions $f$ defined as follows.

######  Definition 6 (Well-behaved).

We say a function $f\colon U^{2}\rightarrow\mathbb{R}$ is well-behaved around
the origin if the following conditions are met.

  * •

$f$ is a $C^{2}$-function, with $U\subseteq\mathbb{R}$ being a neighborhood of
$(0,0)$,

  * •

$f(0,0)=0$, and all partial derivatives $f_{x}$, $f_{y}$, $f_{xx}$, $f_{xy}$
and $f_{yy}$ are rational, in $(0,0)$.

  * •

$f_{x}(0,0)\neq 0$ or $f_{y}(0,0)\neq 0$,

  * •

$f(x,y)$ can be computed on a real RAM [24].

Note that if $p(x,y)$ is a polynomial of the form
$\sum_{i,j}a_{i,j}x^{i}y^{j}$, then $p$ is well-behaved if and only if
$a_{0,0}=0$, $a_{1,0},a_{0,1},a_{2,0},a_{1,1},a_{0,2}$ are rational, and
($a_{1,0}\neq 0$ or $a_{0,1}\neq 0$).

######  Definition 7 (Curved).

Let $f:U^{2}\rightarrow\mathbb{R}$ be a function that is well-behaved around
the origin. We write the curvature of $f$ at zero by

$\kappa=\kappa(f)=\left(\frac{f_{y}^{2}f_{xx}-2f_{x}f_{y}f_{xy}+f_{x}^{2}f_{yy}}{(f_{x}^{2}+f_{y}^{2})^{\frac{3}{2}}}\right)(0,0),$

see Figure 4 for an illustration. We say $f$ is

  * •

curved if $\kappa(f)\neq 0$,

  * •

convexly curved if $\kappa(f)<0$, and

  * •

concavely curved if $\kappa(f)>0$.

Note that we can define the simpler expression
$\kappa^{\prime}=\kappa^{\prime}(f)$

$\kappa^{\prime}(f)=\left(f_{y}^{2}f_{xx}-2f_{x}f_{y}f_{xy}+f_{x}^{2}f_{yy}\right)(0,0),$

and it holds that $\textrm{sign}(\kappa)=\textrm{sign}(\kappa^{\prime})$. For
this reason, we will work with $\kappa^{\prime}$ instead of $\kappa$.

Figure 4: The expression $\kappa(f)$, has a geometric interpretation as the
inverse of the radius of the tangent circle at $(0,0)$. The sign of
$\kappa(f)$ tells us on which side of the curve ($f(x,y)=0$) the circle lies.

Consider a polynomial $p$ of the form $p(x,y)=\sum_{i,j}a_{ij}x^{i}y^{j}$.
Then $\kappa^{\prime}(p)$ equals

$\kappa^{\prime}(p)=a_{01}^{2}a_{20}-a_{10}a_{01}a_{11}+a_{10}^{2}a_{02}.$

Now, we are ready to state our main theorem for equality constraints.

######  Theorem 8.

Let $f\colon U^{2}\rightarrow\mathbb{R}$ be well-behaved and curved around the
origin. Then CE is $\exists\mathbb{R}$-complete, even when $\delta=O(n^{-c})$
for any constant ${c>0}$.

Recall that we assume $\delta$ to be given as part of the input. Note that
$\exists\mathbb{R}$-membership follows from the fact that $f$ is computable on
the real RAM and the structural theorem by Erickson Hoog and Miltzow [24,
Theorem 2.1]. It states that a problem is contained in $\exists\mathbb{R}$, if
and only if there is an algorithm on the real RAM that can verify a given
solution.

Unfortunately, we are only capable of encoding inequality constraints in
geometric packing. Thus, in order to apply our techniques to geometric
packing, we generalize Theorem 8 to inequality constraints. In the following
we define the convex concave inequality problem (CCI), which is completely
analogous to CE with one subtle difference. The constraint $f(x,y)=0$ is
replaced by $f(x,y)\geq 0$ and $g(x,y)\geq 0$. The curved condition is
replaced by convexly curved and concavely curved conditions.

######  Definition 9 (Convex concave inequality problem (CCI)).

We assume that we are given $\delta>0$, a domain $[-\delta,\delta]\subseteq U$
and functions $f,g:U^{2}\rightarrow\mathbb{R}$. Then we define the signature
$C(f,g,\delta)$ as

$C(f,g,\delta)=\\{x+y=z,\;f(x,y)\geq 0,\;g(x,y)\geq 0,\;x\geq
0,\;x=\delta\\}.$

The CCI problem is the CCSP given by $C(f,g,\delta)$. Furthermore, we are
promised that $V(\Phi)\subseteq[-\delta,\delta]^{n}$.

Note that despite its name, we do not make any assumptions on $f,g$ in the
problem definition of CCI. We do this explicitly, as there are various
technical ways to formulate those assumptions. We will use different
assumptions in our proofs culminating in the following theorem.

######  Theorem 10.

Let $f,g\colon U^{2}\to\mathbb{R}$ be two well-behaved functions, one being
convexly curved, and the other being concavely curved. Then the CCI problem is
$\exists\mathbb{R}$-complete, even when $\delta=O(n^{-c})$ for any constant
${c>0}$.

In order to compare Theorem 8 and Theorem 10, consider the following two
signatures for some given well-behaved and curved $f$:

$C_{1}=\\{x+y=z,\ x\geq 0,\ x=\delta,\ f(x,y)=0\\},$

and

$C_{2}=\\{x+y=z,\ x\geq 0,\ x=\delta,\ f(x,y)\geq 0,\ -f(x,y)\geq 0\\}.$

Clearly, $C_{2}$ is more expressive than $C_{1}$. Therefore Theorem 8 implies
a special case of Theorem 10. Namely, the case that $g=-f$. For general $f$
there is no further relation between the two theorems. Yet for the special
case of $f=y-\bar{f}(x)$ it holds that Theorem 10 implies Theorem 8 as
follows. We can encode each constraint of the form $f(x,y)=y-\bar{f}(x)\geq 0$
as follows: $f(x,z_{1})=z_{1}-\bar{f}(x)=0$, $z_{2}=y-z_{1}$, and $z_{2}\geq
0$. Similarly, constraints of the form $-f(x,y)=\bar{f}(x)-y\geq 0$ can be
encoded in $C_{1}$.

###  1.4 Discussion

Theorem 8 and Theorem 10 are a strong generalization of the
$\exists\mathbb{R}$-completeness of ETR-INV. The problem ETR-INV played a
central role both in $\exists\mathbb{R}$-completeness of the Art Gallery
problem [2] and geometric packing [5]. One of the major obstacles of the
$\exists\mathbb{R}$-completeness proofs of the Art Gallery problem was to find
a way to encode inversion. If the authors had known Theorem 8 back then, it
would have been sufficient to find essentially any well-behaved and curved
constraint on two variables, which is much easier.

Let us now discuss further implications of our results and some potential
future research directions.

  * •

We want to point out that addition and convexly curved constraints alone seem
not to be sufficient to establish $\exists\mathbb{R}$-completeness, as convex
programs are believed to be polynomial time solvable. See [37] for an in-depth
discussion.

  * •

When we allow formulas in the first order theory of the reals, it is easier to
describe arbitrary semi-algebraic sets, even when only allowing a single non-
linear constraint. For example, if we allow a single convex constraint
$D=\left\\{(x,y)\in\mathbb{R}^{2}\,\middle|\,x^{2}+y^{2}\leq 1\right\\}$, then
the following formula described the upper half of the boundary of the disk,
given by $\left\\{(x,y)\in\mathbb{R}^{2}\,\middle|\,x^{2}+y^{2}=1\land y\geq
0\right\\}$:

$\varphi(x,y)=D(x,y)\land\forall_{z\in\mathbb{R}}(D(x,z)\Rightarrow z\leq y).$

Using just the language of CCSPs, it is however impossible to encode such a
set using only linear constraints and the constraint $D(x,y)$, as any CCSP
instance of this form describes a convex set. Note in particular that we may
not apply quantifier elimination to the given formula $\varphi$, since this is
impossible without introducing non-linear constraints different from $D(x,y)$.
For a more extensive analysis of the semi-algebraic sets which can be
described using the first order theory of the reals when the set of
constraints is restricted, we refer to [32, 38, 39].

  * •

When we remove the convex constraint, but keep the concave constraint in
Theorem 10 then we do not know if the problem is $\exists\mathbb{R}$-complete.
It is easy though to establish NP-hardness in this case [11]. We consider the
option that there is another complexity class Concave that characterizes such
CCSPs. As with geometric packing with convex pieces, polygonal containers and
translations grant the possibility to encode only linear and concave
constraints. This problem is a natural candidate to be Concave-complete. We
are curious if this intuition could be supported in some mathematically
rigorous way.

  * •

The constraint $x=\delta$ is required in order to establish the range promise.
If we are aiming for a classification that is not interested in range
promises, then we assume that this constraint can be replaced by $x=1$. Note
that without such a constraint, the origin is always a valid solution.

  * •

If we remove the addition constraint, we are left only with constraints in at
most two variables. This seems too weak to establish
$\exists\mathbb{R}$-completeness, as setting $x$ determines $y$, up to
finitely many options once we impose the constraint $f(x,y)=0$. On the other
hand, very large and irrational solutions can be enforced, which makes it
unlikely for those CCSPs to be contained in NP. We wonder whether those CCSPs
can be solved with an oracle to arithmetic circuits and non-determinism.

  * •

Given the discussion above, it seems plausible that at least one ternary
constraint is required to establish $\exists\mathbb{R}$-completeness.
Therefore, the case of CCSPs with exactly one ternary constraint appears
interesting to us. Note that the ternary multiplication constraint $x\cdot
y=z$ can be transformed to the linear constraint $\log x+\log y=\log z$ [13].
Therefore it seems unlikely that the multiplication constraint by itself leads
to $\exists\mathbb{R}$-completeness. (Note that taking $\textrm{exp}(x)$ is an
analytic function that is generally not supported on the real RAM [24].) It is
plausible that this trick or similar tricks can only be applied to exceptional
ternary constraints. Therefore, it may be common that one well-behaved and
curved ternary equality constraint is sufficient to imply
$\exists\mathbb{R}$-completeness.

  * •

We want to point out that we do not consider arbitrary constraints. Otherwise,
we could easily include constraints which enforce that variables are integers,
thereby allowing us to encode arbitrary Diophantine equations. This would make
the problem undecidable. As a consequence any type of classification of
continuous constraints must limit the set of allowed constraints in some way.

  * •

We have in this paper completely neglected the variable-constraint incidence
graph. Previous work showed that this graph can be restricted, by self-
reduction and a clever application of the addition constraint [20, 31]. We are
curious if it is possible to classify hereditary graph classes for which CCI
is $\exists\mathbb{R}$-complete.

  * •

Although $x\geq 0$ may not be necessary to imply
$\exists\mathbb{R}$-completeness, our proof heavily relies on it.

  * •

Previous reductions of $\exists\mathbb{R}$-completeness usually also imply so-
called universality results. They translate topological and algebraic
phenomena from one type of CSP to another type. Our methods seem not to imply
these types of universality results. Specifically, if $f$ is a complicated
function that is not even a polynomial, it seems implausible that $f$ can be
used to construct, say, $\sqrt{2}$.

###  1.5 Proof Overview for CE and CCI

The proof goes into several steps which we explain in the following.

Figure 5: A formal overview of the different steps of the proof to Theorem 8
and Theorem 10.

#### Ball Theorem.

One of the most important tools that we employ is a lemma from real algebraic
geometry. It states that for every ETR-formula $\Phi$ there is a ball $B$
whose radius only depends on the description complexity $L$ of $\Phi$, such
that the following property is satisfied: if $\Phi$ has at least one solution
$x$ then there must be also a solution $y$ inside the ball $B$. This theorem
tells us that solutions cannot get too large. To get an intuition, consider
the system of equations $x_{0}=2,x_{i+1}=x_{i}^{2}$. Clearly,
$x_{n}=2^{2^{n}}$, which is double exponentially large. The ball theorem
essentially states that we cannot get much larger numbers.

#### Range.

To introduce range constraints is common practice and we inherit them from a
previous work [4, 5]. We repeat here the argument, for the benefit of the
reader. In order to restrict the range of every variable, we first note that
the ball theorem already tells us that the range of each variable is limited
by some number $r$. We construct $\varepsilon=\delta/r$ and replace every
variable $x$ by $\left\llbracket\varepsilon x\right\rrbracket=\varepsilon\cdot
x$ and consequently we need to adopt all constraints. For instance $x\cdot
y=z$ becomes $\left\llbracket\varepsilon
x\right\rrbracket\cdot\left\llbracket\varepsilon
y\right\rrbracket=\left\llbracket\varepsilon z\right\rrbracket\varepsilon$. In
this way, we can easily ensure that if there is a solution at all than there
is at least one solution with all variables in the range $[-\delta,\delta]$.

We will make use of this re-scaling trick to place all variables in an even
smaller range close to zero. As the behavior of $f$ and $g$ is better
understood close to the origin. Specifically, the error
$|f(x)-x^{2}|\leq\varepsilon^{3}$ is small enough to pretend that $f$ behaves
like a squaring function.

#### Approximate Solution.

Using the ball theorem, we will establish that equality constraints of the
form $p(x)=0$ can be slightly weakened to $|p(x)|\leq\varepsilon$ for some
sufficiently small $\varepsilon$. To get an intuition consider the following
highly simplified cases.

Assume we have given a polynomial equation $p(x)=0$, with
$p\in\mathbb{Z}[X_{1},\ldots,X_{n}]$ and we are looking for a solution
$x\in\mathbb{Z}^{n}$. Then in particular, we know that for all
$x\in\mathbb{Z}^{n}$ that $p(x)\in\mathbb{Z}$. This readily implies that we
can equivalently ask for some $x\in\mathbb{Z}^{n}$ that satisfies
$|p(x)|\leq\tfrac{1}{2}$. Now, this is trivial for integers as integers have
distance at least one to each other. But we can generalize the same principle
also to rational and algebraic numbers.

Let $S=\\{\frac{a_{1}}{b_{1}},\ldots,\frac{a_{1}}{b_{1}}\\}$ be $n$ rational
numbers with $|a_{i}|,|b_{i}|\leq L$. Thus it is easy to see that $q,r\in S$
have minimum distance $\frac{1}{L^{2}}$. This implies that if
$|q-r|\leq\frac{1}{L^{2}}$, for some $q,r\in S$, we can infer that $q=r$.
Again, this may seem almost trivial, but relies on the simple fact that
rational numbers with bounded description complexity have a minimum distance
to one another.

Lemma 15 generalizes the idea to algebraic numbers. Using the ball theorem, we
will establish that algebraic numbers also have some minimum distance to one
another, if we restrict their description complexity.

#### ETR-SQUARE.

We use a theorem by Abrahamsen and Miltzow that shows that ETR-SQUARE is
$\exists\mathbb{R}$-complete [4]. In this variant, we essentially have only
addition ($x+y=z$) and squaring constraints ($x^{2}=y$). Furthermore, the
range of each variable is restricted to a small range around zero.

#### Explicit.

Given those tools, we can show that we can replace a squaring constraint by
explicit constraints ($f(x)=y$). We start by only considering $f$ which
satisfy

$|f(x)-x^{2}|\leq\frac{1}{10}x^{3}.$ (1)

The idea of the reduction from ETR-SQUARE is simple, but tedious. We can
rewrite the constraint $x^{2}=y$ as a linear combination of squares as follows

$1^{2}+2x^{2}+y^{2}-(1+y)^{2}=0.$

Now, we can replace each square using the function $f$ to
$f(1)+2f(x)+f(y)-f(1+y)=0$ As $f$ is approximately squaring, this implies that
we are approximately enforcing the constraint $x^{2}=y$. In other words, we
enforce $|x^{2}-y|\leq\varepsilon$. Note that this is the technically most
tedious step to make rigorous as we will later see. As we have discussed above
it is sufficient to enforce each constraint approximately. The technical
difficulty is many-fold. We need to work with scaled variables, instead of the
original variables. Furthermore, we have to take into consideration that when
we construct $\varepsilon$ that this also makes the formula longer. In
particular this means that definition of $\varepsilon$ cannot depend on the
newly constructed instance, but has to depend on the original instance.

Using linear transformations and Taylor expansion on $f$, we can replace
Equation 1 relatively easily by Equation 2

$f\textrm{ twice differentiable and, }f^{\prime\prime}(0)>0$ (2)

Figure 6: The implicit function theorem tells us that there is an function
$f_{\textrm{expl}}$ such that the curve $y=f_{\textrm{expl}}(x)$ is locally
identical to the curve $f(x,y)=0$.

#### Implicit.

We are now ready to handle the more general case of constraints in implicit
form ($f(x,y)=0$). The implicit function theorem tells us that there is a
function $f_{\textrm{expl}}$ such that the curve $y=f_{\textrm{expl}}(x)$ is
locally identical to the curve $f(x,y)=0$, see Figure 6. The properties of the
partial derivatives of $f$ translate to properties of the partial derivatives
of $f_{\textrm{expl}}$. In this way, we can infer hardness of the CSP with
constraint $f(x,y)=0$ from the problem with constraint
$y=f_{\textrm{expl}}(x)$.

#### Computability of $f_{\textrm{expl}}$.

Interestingly, the fact that $f$ is computable does not readily imply that
$f_{\textrm{expl}}$ is computable as well. Yet, we only require that we can
test $f_{\textrm{expl}}(x)=y$, which is equivalent to $f(x,y)=0$. And by
definition we can compute $f(x,y)$.

#### Inequalities.

The case of inequalities goes analogous to the equality case. We need one
convexly curved and one concavely curved inequality. Whenever we want to upper
bound an expression, we use one inequality and whenever we need to lower bound
something, we use the other one. While on the surface this is not so
difficult, it makes the reduction considerably more tedious. Specifically, it
makes it harder to have an intuition on several technical steps and the
meaning of several intermediate variables.

###  1.6 Proof Overview to Packing

We are following the framework by Abrahamsen et al. [5], with a few
modifications. Instead of solely using the inversion constraint, we use, up to
linear transformations, the following two constraints

$x\cdot y\geq 1,\quad x^{2}+y^{2}\geq 1$

Theorem 10 tells us that those two constraints are sufficient to establish
$\exists\mathbb{R}$-completeness of geometric packing. While there is already
a gadget for the first one, we needed to construct a new gadget for the second
constraint.

Figure 7: The idea of the gramophone construction. (For black and white
printouts, see Figure 14 for color-codes.)

Consider Figure 7 for the following description. The core idea is to have a
rectangle rotate around a pivot point $p$. Thus the tip $c$ of a second piece
is constrained to lie on a circle around $p$, see Figure 7 a. To be precise
$c$ has distance at least $1$ from $p$. As a second step, we refine the
construction such that we can read of the $x$ and $y$-coordinate of $c$ with
the help of other pieces (yellow and blue), see Figure 7 b. In a third step,
we need to modify this construction such that the slack is extremely low and
every piece is fingerprinted. This also involves some modifications at other
parts of the construction so that the fingerprinting is not interfering with
the vertical edge-edge contact between the pink and yellow piece, see Figure 7
c.

#### Acknowledgment.

We thank Eunjung Kim and Saoirsé Freeney for helpful comments. The first
author is generously supported by the NWO Veni grant EAGER.

##  2 Proof of CCSP-Theorems

In this section, we will prove Theorem 8 and Theorem 10.

###  2.1 Approximate Solutions

In this section, we show that if all constraints are “almost satisfied”, then
all constraints are also “exactly satisfied”. We start by considering the
following problem, which is a special case of the problem ETR-SMALL from [5,
Definition 36]:

######  Definition 11 (ETR-AMI-$\frac{1}{2}$).

We define the set of constraints $C_{\mathrm{AMI}}$ as

$C_{\mathrm{AMI}}=\left\\{x+y=z,\;x\cdot y=z,\;x\geq
0,\;x=\tfrac{1}{2}\right\\}$

Now we define the ETR-AMI-$\frac{1}{2}$ problem as the CCSP given by
$C_{\mathrm{AMI}}$. Furthermore, we are promised that
$V(\Phi)\subseteq\left[-\frac{1}{2},\frac{1}{2}\right]$.

We will not repeat the hardness proof of this problem here. Instead we refer
to [5, Lemma D], where a full proof is given.

######  Lemma 12 ([5]).

The problem ETR-AMI-$\frac{1}{2}$ is $\exists\mathbb{R}$-hard.

From here, we can prove hardness of the following problem:

######  Definition 13 (ETR-SQUARE-1).

We define the set of constraints $C_{\mathrm{SQUARE}}$ as

$C_{\mathrm{SQUARE}}=\left\\{x+y=z,\;y=x^{2},\;x\geq 0,\;x=1\right\\}.$

Now we define the ETR-SQUARE-1 problem as the CCSP given by
$C_{\mathrm{SQUARE}}$. Furthermore, we are promised that
$V(\Phi)\subseteq[-1,1]$.

Before we start the proof of $\exists\mathbb{R}$-hardness of ETR-SQUARE-1, we
make some remarks about the notation used in this and future proofs. In those
proofs, newly introduced variables will often be denoted by using double
square brackets, like this: $\left\llbracket x^{2}\right\rrbracket$. In this
notation, formally the whole expression including the brackets and the symbols
within it should be understood as the name of the variable, without any
special meaning. The symbols within the brackets will usually denote the value
which is intuitively represented by the variable.

######  Lemma 14.

The problem ETR-SQUARE-1 is $\exists\mathbb{R}$-hard.

###### Proof.

We start with an ETR-AMI-$\frac{1}{2}$ instance $\Phi$. To this instance we
add a variable $\left\llbracket 1\right\rrbracket$ and a constraint
$\left\llbracket 1\right\rrbracket=1$. Next we replace every constraint of the
form $x=\frac{1}{2}$ by a constraint $x+x=\left\llbracket 1\right\rrbracket$.
Finally, for every constraint of the form $x\cdot y=z$, we introduce the
following new variables:

$\left\llbracket x^{2}\right\rrbracket,\left\llbracket
y^{2}\right\rrbracket,\left\llbracket
x+y\right\rrbracket,\left\llbracket(x+y)^{2}\right\rrbracket,\left\llbracket
x^{2}+2xy\right\rrbracket,\left\llbracket 2xy\right\rrbracket,\left\llbracket
xy\right\rrbracket$

and we add the following constraints:

$\displaystyle\left\llbracket x^{2}\right\rrbracket$ $\displaystyle=x^{2}$
$\displaystyle\left\llbracket y^{2}\right\rrbracket$ $\displaystyle=y^{2}$
$\displaystyle\left\llbracket x+y\right\rrbracket$ $\displaystyle=x+y$
$\displaystyle\left\llbracket(x+y)^{2}\right\rrbracket$
$\displaystyle=\left\llbracket x+y\right\rrbracket^{2}$
$\displaystyle\left\llbracket(x+y)^{2}\right\rrbracket$
$\displaystyle=\left\llbracket x^{2}+2xy\right\rrbracket+\left\llbracket
y^{2}\right\rrbracket$ $\displaystyle\left\llbracket
x^{2}+2xy\right\rrbracket$ $\displaystyle=\left\llbracket
x^{2}\right\rrbracket+\left\llbracket 2xy\right\rrbracket$
$\displaystyle\left\llbracket 2xy\right\rrbracket$
$\displaystyle=\left\llbracket xy\right\rrbracket+\left\llbracket
xy\right\rrbracket$ $\displaystyle\left\llbracket xy\right\rrbracket$
$\displaystyle=z.$

Every constraint of the form $x+y=z$ or $x\geq 0$ is not changed. After
performing all these changes, which only needs linear time, we have an ETR-
SQUARE-1 formula $\Psi$. Furthermore, it can be checked that every solution of
this ETR-SQUARE-1 formula corresponds uniquely to a solution of the original
ETR-AMI-$\frac{1}{2}$ formula. Also the fact that
$V(\Phi)\subseteq[-1/2,1/2]^{n}$ can be seen to imply that
$V(\Psi)\subseteq[1,1]^{m}$, where $m$ is the number of variables in $\Psi$.
This proves that $\Psi$ is an ETR-SQUARE-1 instance which is equivalent to the
original ETR-AMI-$\frac{1}{2}$ instance. Therefore the reduction is valid, and
the problem ETR-SQUARE-1 is $\exists\mathbb{R}$-hard. ∎

Next we will state the main lemma of this section. This lemma intuitively
states the following: if an ETR-SQUARE-1 formula $\Phi$ has something which is
“almost a solution”, with an error of at most $2^{-2^{O(|\Phi|)}}$, then
$\Phi$ also admits an actual solution.

######  Lemma 15.

Let $\Phi=\Phi(x_{1},\ldots,x_{n})$ be a ETR-SQUARE-1 formula such that
$V(\Phi)\subseteq[-1,1]^{n}$. Define $\Phi_{\varepsilon}$ as the formula where
every constraint of the form $y=x^{2}$ is replaced by a constraint of the form
$|y-x^{2}|\leq\varepsilon$, and where constraints $-1\leq x\leq 1$ are added
for every $x\in\\{x_{1},\ldots,x_{n}\\}$.

Now there exists a constant $M\in\mathbb{Z}$ with $M=O(|\Phi|)$, such that if
we take $\varepsilon=2^{-2^{M}}$, then $V(\Phi_{\varepsilon})\neq\emptyset$ if
and only if $V(\Phi)\neq\emptyset$.

The proof of this lemma requires a result from real algebraic geometry. The
formulation here is taken from [5, Corollary 37], which is in turn based on a
statement from [6].

######  Corollary 16.

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

###### Proof (of Lemma 15).

Consider the formula $\Psi$ which is obtained from $\Phi$ by adding
constraints $-\delta\leq x\leq\delta$ for each $x\in\\{x_{1},\ldots,x_{n}\\}$,
replacing every constraint $y=x^{2}$ in $\Phi$ by a constraint
$y+\eta_{i}=x^{2}$, where $\eta_{i}$ is a new variable (we add one such
variable for each original squaring constraint), adding a new variable $u$,
and finally adding a constraint

$u(\eta_{1}^{2}+\eta_{2}^{2}+\cdots+\eta_{r}^{2})=1.$

In this way, after choosing values for all original variables from $\Phi$, the
new variable $u$ encodes the inverse of the total squared error in all
squaring constraints. Now it can be seen that $V(\Psi)$ is bounded if and only
if $V(\Phi)=\emptyset$. In the case where $V(\Psi)$ is bounded, we have by
Corollary 16 the upper bound $u\leq 2^{2^{L+5}}$ where $L$ is the complexity
of $\Psi$, which is linear in the complexity of $\Phi$.

We take $M$ to be an integer such that $r\cdot 2^{-2^{M+1}}<2^{-2^{L+5}}$,
note that this can be achieved while keeping $M$ bounded by a linear
polynomial in the size of $\Phi$. Also let $\varepsilon=2^{-2^{M}}$, so
$r\varepsilon^{2}<2^{-2^{L+5}}$.

Suppose that $V(\Phi_{\varepsilon})\neq\emptyset$, let $P\in
V(\Phi_{\varepsilon})$. Now we can obtain a point in $P^{\prime}\in V(\Psi)$
which has the same values of each of the $x_{i}$’s as $P$, and which has the
unique values of $\eta_{i}$ and $u$ that make all constraints hold. Using
$P\in V(\Phi_{\varepsilon})$, it can be seen that all values of the $\eta_{i}$
of $P^{\prime}$ are at most $\varepsilon$. This implies that the value of
$\eta_{1}^{2}+\cdots+\eta_{r}^{2}$ is at most $r\varepsilon^{2}<2^{-2^{L+5}}$,
and therefore the value of $u$ corresponding to $P^{\prime}$ is larger than
$2^{2^{L+5}}$. So $V(\Psi)$ contains a point with distance from the origin
larger than $2^{2^{L+5}}$. This implies that $V(\Psi)$ is not bounded, and
therefore $V(\Phi)\neq\emptyset$.

So $V(\Phi_{\varepsilon})\neq\emptyset$ implies $V(\Phi)\neq\emptyset$. We
also know that $V(\Phi)\neq\emptyset$ implies that
$V(\Phi_{\varepsilon})\neq\emptyset$, since $V(\Phi)\subseteq
V(\Phi_{\varepsilon})$. This completes the proof of the lemma. ∎

###  2.2 Almost Square Explicit Equality Constraints

Using Lemma 15, we are able to prove that an explicit version CE is also
$\exists\mathbb{R}$-complete, with some additional assumptions. Note that this
subsection is technically not needed for the proof of Theorem 8 and Theorem
10. We will prove a similar lemma also for the inequality case. And the
inequality case can be used to also prove the equality case. Yet, we believe
that seeing the proof first for the equality case makes it much easier to read
Section 2.4.

######  Definition 17 (CE-EXPL).

Let $f\colon U\to\mathbb{R}$ be a function. Now we define the CE-EXPL problem
to be the CE problem corresponding to the function $f^{*}\colon
U^{2}\to\mathbb{R}$ defined by $f^{*}(x,y)=y-f(x)$.

The goal of this section is to prove the following result:

######  Lemma 18.

Let $U\subseteq\mathbb{R}$ be a neighborhood of $0$, and let $f\colon
U\to\mathbb{R}$ be a function such that $|f(x)-x^{2}|\leq\frac{1}{10}|x|^{3}$
for all $x\in U\subseteq\mathbb{R}$. Now the problem CE-EXPL is
$\exists\mathbb{R}$-complete, even if $\delta=O(n^{-c})$ for any constant
$c>0$.

The reason that we impose these specific constraints on $f$, which enforce $f$
to be very similar to squaring, is that the proof will use
$\exists\mathbb{R}$-hardness of a problem involving a squaring constraint.
Furthermore, this specific case can be generalized to more general functions
$f$.

###### Proof.

Before giving the details of the construction, we will first give an overview
of the used approach. The idea of this proof is to start with an instance of
ETR-SQUARE-1, and convert this into a CE-EXPL instance by using $f$ to
approximate squaring. In order to ensure that $f$ approximates squaring close
enough, the whole instance is scaled by some small factor $\varepsilon$, so
every variable $x$ is replaced by a variable representing $\varepsilon x$
instead.

The linear constraints and inequalities are easy to rewrite in terms of
$\varepsilon x$, for example a constraint of the form $x+y=z$ can be rewritten
to $\varepsilon x+\varepsilon y=\varepsilon z$.

Handling a squaring constraint $y=x^{2}$ is a bit more complicated. The first
step is to rewrite this to a constraint involving $\varepsilon x$ and
$\varepsilon y$, we get $\varepsilon\cdot\varepsilon y=(\varepsilon x)^{2}$.
However, in the CE-EXPL problem there is no easy way to simulate the
multiplication on the left-hand side of this equation. To solve this, we
rewrite this equation to only use sums and differences of squares:

$\varepsilon^{2}+2(\varepsilon x)^{2}+(\varepsilon
y)^{2}-(\varepsilon+\varepsilon y)^{2}=0.$

To simplify notation a bit, we will denote $t_{1}=\varepsilon$,
$t_{2}=\varepsilon x$, $t_{3}=\varepsilon y$ and
$t_{4}=\varepsilon+\varepsilon y$. Using this notation the equation becomes
$t_{1}^{2}+2t_{2}^{2}+t_{3}^{2}-t_{4}^{2}=0$. This is still not something we
can directly enforce in a CE formula. However, by applying the function $f$,
squaring can be approximated. Furthermore, Lemma 15 on a high level implies
that such an approximation is enough to guarantee existence of a solution to
the original equations. This is why in the CE formulation we enforce

$f(t_{1})+2f(t_{2})+f(t_{3})-f(t_{4})=O(\varepsilon^{3}).$ (3)

Enforcing the $=O(\varepsilon^{3})$ presents another problem: we cannot easily
compute $\varepsilon^{3}$. To counter this, we instead bound the left-hand
side of the equation in absolute value by
$2(f(\varepsilon+f(\varepsilon))-f(\varepsilon))$, which is approximately
equal to $4\varepsilon^{3}$ (note that in the case that $f(x)=x^{2}$ for all
$x$, this expression would actually be equal to
$4\varepsilon^{3}+2\varepsilon^{4}$). The details of this reduction and a
proof of its correctness will be worked out in the remainder of this proof.

#### Reduction.

Let $\Phi$ be an ETR-SQUARE-1 formula. We pick some $\delta>0$ such that
$\delta<\frac{1}{4}$, and which furthermore satisfies the additional
constraint $\delta=O(n^{-c})$ if required (how we choose $\delta$ does not
matter, as long as is satisfies these constraints). We will now construct a CE
formula $\Psi$ such that $V(\Phi)\neq\emptyset$ if and only if
$V(\Psi)\neq\emptyset$.

Let $M$ be the constant obtained by applying Lemma 15 to $\Phi$, and let $L$
be the smallest positive integer such that $2^{-2^{L}}\leq\frac{1}{100}\cdot
2^{-2^{M}}$ and $2^{-2^{L}}\leq\frac{1}{100}$. We start by introducing
variables $\left\llbracket\delta_{i}\right\rrbracket$ for $0\leq i\leq L$. The
variable $\left\llbracket\delta_{0}\right\rrbracket$ satisfies the constraint
$\left\llbracket\delta_{0}\right\rrbracket=\delta$, and for each $1\leq i\leq
L$ we add a constraint

$\left\llbracket\delta_{i}\right\rrbracket=f(\left\llbracket\delta_{i-1}\right\rrbracket).$

Denote
$\left\llbracket\varepsilon\right\rrbracket=\left\llbracket\delta_{L}\right\rrbracket$.
The idea behind these definitions is to simulate repeated squaring, as we will
see later they force the value of $\left\llbracket\varepsilon\right\rrbracket$
to be in the interval $\left(0,2^{-2^{L}}\right]$.

Next, we introduce a new variable $\left\llbracket\approx
2\varepsilon^{3}\right\rrbracket$ together with a (constant) number of
constraints and auxiliary variables that enforce

$\left\llbracket\approx
2\varepsilon^{3}\right\rrbracket=f(\left\llbracket\varepsilon\right\rrbracket+f(\left\llbracket\varepsilon\right\rrbracket))-f(\left\llbracket\varepsilon\right\rrbracket).$

This can be done explicitly by introducing auxiliary variables
$\left\llbracket f(\varepsilon)\right\rrbracket$,
$\left\llbracket\varepsilon+f(\varepsilon)\right\rrbracket$ and
$\left\llbracket f(\varepsilon+f(\varepsilon))\right\rrbracket$ and adding the
following constraints:

$\displaystyle\left\llbracket f(\varepsilon)\right\rrbracket$
$\displaystyle=f(\left\llbracket\varepsilon\right\rrbracket)$
$\displaystyle\left\llbracket\varepsilon+f(\varepsilon)\right\rrbracket$
$\displaystyle=\left\llbracket\varepsilon\right\rrbracket+\left\llbracket
f(\varepsilon)\right\rrbracket$ $\displaystyle\left\llbracket
f(\varepsilon+f(\varepsilon))\right\rrbracket$
$\displaystyle=f(\left\llbracket\varepsilon+f(\varepsilon)\right\rrbracket)$
$\displaystyle\left\llbracket f(\varepsilon+f(\varepsilon))\right\rrbracket$
$\displaystyle=\left\llbracket\approx
2\varepsilon^{3}\right\rrbracket+\left\llbracket
f(\varepsilon)\right\rrbracket.$

In the rest of this proof, and in future proofs of this paper, we will not
give such explicit constraints anymore. The variable $\left\llbracket\approx
2\varepsilon^{3}\right\rrbracket$ will be used to bound the error on the
constraints replacing squaring constraints, as mentioned in the overview of
this proof. Stated differently, it replaces the “$=O(\varepsilon^{3})$” part
of Equation 3.

Now, for each variable $x$ of $\Phi$, we add a variable
$\left\llbracket\varepsilon x\right\rrbracket$ to $\Psi$, together with some
constraints which enforce that
$-\left\llbracket\varepsilon\right\rrbracket\leq\left\llbracket\varepsilon
x\right\rrbracket\leq\left\llbracket\varepsilon\right\rrbracket$. Furthermore
each constraint $x+y=z$ is replaced by $\left\llbracket\varepsilon
x\right\rrbracket+\left\llbracket\varepsilon
y\right\rrbracket=\left\llbracket\varepsilon z\right\rrbracket$, each
constraint $x\geq 0$ is replaced by $\left\llbracket\varepsilon
x\right\rrbracket\geq 0$ and each constraint $x=1$ is replaced by
$\left\llbracket\varepsilon
x\right\rrbracket=\left\llbracket\varepsilon\right\rrbracket$.

For each constraint $y=x^{2}$, we build Equation 3 as in the overview. To do
this, we first introduce variables $\left\llbracket t_{1}\right\rrbracket$,
$\left\llbracket t_{2}\right\rrbracket$, $\left\llbracket
t_{3}\right\rrbracket$ and $\left\llbracket t_{4}\right\rrbracket$ satisfying

$\displaystyle\left\llbracket t_{1}\right\rrbracket$
$\displaystyle=\left\llbracket\varepsilon\right\rrbracket$
$\displaystyle\left\llbracket t_{2}\right\rrbracket$
$\displaystyle=\left\llbracket\varepsilon x\right\rrbracket$
$\displaystyle\left\llbracket t_{3}\right\rrbracket$
$\displaystyle=\left\llbracket\varepsilon y\right\rrbracket$
$\displaystyle\left\llbracket t_{4}\right\rrbracket$
$\displaystyle=\left\llbracket\varepsilon\right\rrbracket+\left\llbracket\varepsilon
y\right\rrbracket.$

(Note that, even though $x$ and $y$ are suppressed in the notation here, the
variables $\left\llbracket t_{1}\right\rrbracket$, $\left\llbracket
t_{2}\right\rrbracket$, $\left\llbracket t_{3}\right\rrbracket$ and
$\left\llbracket t_{4}\right\rrbracket$ should actually be distinct variables
for each constraint $y=x^{2}$.) Next we introduce a new variable
$\left\llbracket\eta_{x,y}\right\rrbracket$ representing the left-hand side of
Equation 3:

$\left\llbracket\eta_{x,y}\right\rrbracket=f(\left\llbracket\varepsilon\right\rrbracket)+2f(\left\llbracket\varepsilon
x\right\rrbracket)+f(\left\llbracket\varepsilon
y\right\rrbracket)-f(\left\llbracket\varepsilon\right\rrbracket+\left\llbracket\varepsilon
y\right\rrbracket).$

The next step is to bound this variable, for this we add constraints which
enforce

$\displaystyle\left\llbracket\eta_{x,y}\right\rrbracket$
$\displaystyle\geq-2\left\llbracket\approx
2\varepsilon^{3}\right\rrbracket\quad\text{and}$
$\displaystyle\left\llbracket\eta_{x,y}\right\rrbracket$ $\displaystyle\leq
2\left\llbracket\approx 2\varepsilon^{3}\right\rrbracket.$

This completes the construction of $\Psi$. Note that in this construction,
every constraint of $\Phi$ is replaced by a constant number of constraints in
$\Psi$, and therefore we have $|\Psi|=O(|\Phi|)$. In particular this reduction
can be executed in linear time.

#### Calculations.

To show validity of the reduction, we first perform some side calculations. We
define $\delta_{0}=\delta$, for $1\leq i\leq L$ we take
$\delta_{i}=f(\delta_{i-1})$, and we take $\varepsilon=\delta_{L}$. We use the
following facts:

$\displaystyle|f(x)-x^{2}|$ $\displaystyle\leq\frac{1}{10}|x|^{3}$
$\displaystyle\text{for }x\in[-\delta,\delta]\setminus\\{0\\}$ (4)
$\displaystyle 0$ $\displaystyle<f(x)\leq 2x^{2}$ $\displaystyle\text{for
}x\in[-\delta,\delta]\setminus\\{0\\}$ (5) $\displaystyle\varepsilon$
$\displaystyle\leq\frac{1}{100}\min\left(2^{-2^{M}},\delta\right)$ (6)
$\displaystyle f(\varepsilon)$ $\displaystyle<\varepsilon$ (7) $\displaystyle
f(\varepsilon+f(\varepsilon))-f(\varepsilon)$
$\displaystyle\in[\varepsilon^{3},3\varepsilon^{3}]$ (8)

Equation 4 is one of the assumptions, and is repeated here just for clarity.
Combining this with $\delta\leq\frac{1}{4}$, Equation 5 follows.

Using induction with the fact that $0<f(x)\leq 2x^{2}$ for
$x\in[-\delta,\delta]\setminus\\{0\\}$, it follows that $0<\delta_{i}\leq
2^{-2^{i}-1}$ for all $i$, so $0<\varepsilon\leq\frac{1}{2}2^{-2^{L}}$. Using
the definition of $L$, we get Equation 6. The fact
$f(\varepsilon)<\varepsilon$ now follows from Equations 5 and 6.

For deriving Equation 8, we first rewrite by adding and subtracting some
terms, and applying the triangle inequality:

$\displaystyle|f(\varepsilon+f(\varepsilon))-f(\varepsilon)-2\varepsilon^{3}|$
$\displaystyle=|f(\varepsilon+f(\varepsilon))-(\varepsilon+f(\varepsilon))^{2}+\varepsilon^{2}-f(\varepsilon)$
$\displaystyle\quad\;+(f(\varepsilon)+\varepsilon^{2})(f(\varepsilon)-\varepsilon^{2})+\varepsilon^{4}+2\varepsilon(f(\varepsilon)-\varepsilon^{2})|$
$\displaystyle\leq|f(\varepsilon+f(\varepsilon))-(\varepsilon+f(\varepsilon))^{2}|+|\varepsilon^{2}-f(\varepsilon)|$
$\displaystyle\quad\;+(f(\varepsilon)+\varepsilon^{2})|f(\varepsilon)-\varepsilon^{2}|+\varepsilon^{4}+2\varepsilon|f(\varepsilon)-\varepsilon^{2}|.$

To this we apply Equations 4, 6 and 7 to obtain the desired bound:

$\displaystyle|f(\varepsilon+f(\varepsilon))-f(\varepsilon)-2\varepsilon^{3}|$
$\displaystyle\leq|f(\varepsilon+f(\varepsilon))-(\varepsilon+f(\varepsilon))^{2}|+|\varepsilon^{2}-f(\varepsilon)|$
$\displaystyle\quad\;+(f(\varepsilon)+\varepsilon^{2})|f(\varepsilon)-\varepsilon^{2}|+\varepsilon^{4}+2\varepsilon|f(\varepsilon)-\varepsilon^{2}|$
$\displaystyle\leq\frac{1}{10}(\varepsilon+f(\varepsilon))^{3}+\frac{1}{10}\varepsilon^{3}+(f(\varepsilon)+\varepsilon^{2})\varepsilon^{3}+\varepsilon^{4}+\frac{1}{5}\varepsilon^{4}$
$\displaystyle\leq\frac{8}{10}\varepsilon^{3}+\frac{1}{10}\varepsilon^{3}+\frac{1}{10}\varepsilon^{3}$
$\displaystyle\leq\varepsilon^{3},$

so
$f(\varepsilon+f(\varepsilon))-f(\varepsilon)\in[\varepsilon^{3},3\varepsilon^{3}]$.

####  $V(\Phi)$ nonempty implies $V(\Psi)$ nonempty.

Now we can start to prove the validity of the reduction. First suppose that
$V(\Phi)\neq\emptyset$, so there is some $P\in V(\Phi)$. It needs to be shown
that also $V(\Psi)\neq\emptyset$, to do this we construct a point $Q\in
V(\Psi)$. For a variable $x$ of $\Phi$, we will use the notation $x(P)$ for
the value of this variable for the point $P$. Similar notation is used for
$Q$. To define $Q$, we take $\left\llbracket\varepsilon
x\right\rrbracket(Q)=\varepsilon x(P)$ for all variables $x$ of $\Phi$, and we
enforce that $Q$ satisfies all equality constraints of $\Psi$. This uniquely
defines the value of $Q$ in all other variables of $\Psi$. In particular, we
get that

$\displaystyle\left\llbracket\varepsilon\right\rrbracket(Q)$
$\displaystyle=\varepsilon$ $\displaystyle\left\llbracket\approx
2\varepsilon^{3}\right\rrbracket(Q)$
$\displaystyle=f(\varepsilon+f(\varepsilon))-f(\varepsilon)$
$\displaystyle\left\llbracket\eta_{x,y}\right\rrbracket(Q)$
$\displaystyle=f(\varepsilon)+2f(\varepsilon x(P))+f(\varepsilon
y(P))-f(\varepsilon+\varepsilon y(P)),$

where the last equality holds for all constraints $y=x^{2}$ in $\Phi$.

It is left to show that $Q$ also satisfies all inequalities of $\Psi$. There
are three types of these inequalities. Firstly, we have inequalities which
enforce $|\left\llbracket\varepsilon
x\right\rrbracket(Q)|\leq\left\llbracket\varepsilon\right\rrbracket(Q)$. That
these are satisfied for $Q$ follows from the fact that $|x(P)|\leq 1$ since
$\Phi$ is a $1$-ETR-SMALL-SQUARE formula. Secondly, for every inequality
$x\geq 0$ in $\Phi$, we get a corresponding inequality
$\left\llbracket\varepsilon x\right\rrbracket\geq 0$, that this is satisfied
follows by combining $\left\llbracket\varepsilon
x\right\rrbracket(Q)=\varepsilon x(P)$ and $x(P)\geq 0$.

Finally, for every constraint $y=x^{2}$ in $\Phi$ we get constraints enforcing
$|\left\llbracket\eta_{x,y}\right\rrbracket|\leq 2\left\llbracket\approx
2\varepsilon^{3}\right\rrbracket$. To see that these are satisfied, first we
shorten the notation a bit by writing $t_{1}=\left\llbracket
t_{1}\right\rrbracket(Q)=\varepsilon$, $t_{2}=\left\llbracket
t_{2}\right\rrbracket(Q)=\varepsilon x(P)$, $t_{3}=\left\llbracket
t_{3}\right\rrbracket(Q)=\varepsilon y(P)$ and $t_{4}=\left\llbracket
t_{4}\right\rrbracket(Q)=\varepsilon+\varepsilon y(P)$. Now
$\left\llbracket\eta_{x,y}\right\rrbracket(Q)$ can be bounded, for this we
first use the triangle inequality:

$\displaystyle|\left\llbracket\eta_{x,y}\right\rrbracket(Q)|$
$\displaystyle=|f(t_{1})+2f(t_{2})+f(t_{3})-f(t_{4})|$
$\displaystyle=|f(t_{1})-t_{1}^{2}+2(f(t_{2})-t_{2}^{2})+f(t_{3})-t_{3}^{2}-(f(t_{4})-t_{4}^{2})$
$\displaystyle\quad\;+t_{1}^{2}+2t_{2}^{2}+t_{3}^{2}-t_{4}^{2}|$
$\displaystyle\leq|f(t_{1})-t_{1}^{2}|+2|f(t_{2})-t_{2}^{2}|+|f(t_{3})-t_{3}^{2}|+|f(t_{4})-t_{4}^{2}|$
$\displaystyle\quad\;+|t_{1}^{2}+2t_{2}^{2}+t_{3}^{2}-t_{4}^{2}|$

Note that $t_{1},t_{2},t_{3}$ and $t_{4}$ were chosen in such a way to ensure
that, given $y(P)=x(P)^{2}$, we have
$t_{1}^{2}+2t_{2}^{2}+t_{3}^{2}-t_{4}^{2}=0$. Using this together with
Equation 4 and the facts that $t_{1}$, $t_{2}$ and $t_{3}$ are bounded in
absolute value by $\varepsilon$, and $t_{4}$ is bounded in absolute value by
$2\varepsilon$, we find

$\displaystyle|\left\llbracket\eta_{x,y}\right\rrbracket(Q)|$
$\displaystyle\leq|f(t_{1})-t_{1}^{2}|+2|f(t_{2})-t_{2}^{2}|+|f(t_{3})-t_{3}^{2}|+|f(t_{4})-t_{4}^{2}|$
$\displaystyle\quad\;+|t_{1}^{2}+2t_{2}^{2}+t_{3}^{2}-t_{4}^{2}|$
$\displaystyle\leq\frac{1}{10}t_{1}^{3}+\frac{1}{5}t_{2}^{3}+\frac{1}{10}t_{3}^{3}+\frac{1}{10}t_{4}^{3}+0$
$\displaystyle\leq\frac{6}{5}\varepsilon^{3}.$

Finally using Equation 8 we derive

$\displaystyle|\left\llbracket\eta_{x,y}\right\rrbracket(Q)|$
$\displaystyle\leq\frac{6}{5}\varepsilon^{3}$ $\displaystyle\leq
2(f(\varepsilon+f(\varepsilon))-f(\varepsilon)).$

This completes the proof that $Q\in V(\Psi)$, so $V(\Psi)\neq\emptyset$.

####  $V(\Psi)$ nonempty implies $V(\Phi)$ nonempty.

Next, suppose that there is some $Q\in V(\Psi)$, now we want to show that
$|x(Q)|\leq\delta$ for all variables $x$ in $\Psi$, and we want to prove that
$V(\Phi)\neq\emptyset$. We start by bounding the coordinates. Note that
$\left\llbracket\varepsilon\right\rrbracket(Q)=\varepsilon$, now for every
variable $x$ of $\Phi$ it follows that $|\left\llbracket\varepsilon
x\right\rrbracket(Q)|\leq|\left\llbracket\varepsilon\right\rrbracket(Q)|\leq\varepsilon$.
Using this, it can be shown that also all values of the auxiliary variables
except for the $\left\llbracket\delta_{i}\right\rrbracket$ are bounded by
$100\varepsilon\leq\delta$. The values
$\left\llbracket\delta_{i}\right\rrbracket(Q)=\delta_{i}$ are furthermore also
all smaller than $\delta$, so this shows that $Q$ is contained in
$[-\delta,\delta]^{m}$, where $m$ is the number of variables of $\Psi$.

Now we need to show that $V(\Phi)\neq\emptyset$. For this we use Lemma 15, we
construct a point $P$ in $V(\Phi_{100\varepsilon})$, which implies
$V(\Phi)\neq\emptyset$ since $100\varepsilon\leq 2^{-2^{M}}$. We define the
point $P$ by taking $x(P)=\frac{\left\llbracket\varepsilon
x\right\rrbracket(Q)}{\varepsilon}$ for all variables $x$ of $\Phi$. It
immediately follows that $P$ satisfies all linear constraints and inequality
constraints of $\Phi$, it is only left to check that it satisfies the
constraints $|y-x^{2}|\leq 100\varepsilon$ of $\Phi_{100\varepsilon}$. To do
this, first we observe that, using Equation 8,

$\displaystyle|\left\llbracket\eta_{x,y}\right\rrbracket(Q)|$
$\displaystyle\leq 2\left\llbracket\approx
2\varepsilon^{3}\right\rrbracket(Q)$
$\displaystyle=2(f(\varepsilon+f(\varepsilon))-f(\varepsilon))$
$\displaystyle\leq 6\varepsilon^{3}.$

Now we will try to bound $|y(P)-x(P)^{2}|$. First we again write
$t_{1}=\left\llbracket t_{1}\right\rrbracket(Q)=\varepsilon$,
$t_{2}=\left\llbracket t_{2}\right\rrbracket(Q)=\varepsilon x(P)$,
$t_{3}=\left\llbracket t_{3}\right\rrbracket(Q)=\varepsilon y(P)$ and
$t_{4}=\left\llbracket t_{4}\right\rrbracket(Q)=\varepsilon+\varepsilon y(P)$.
These choices were made such that

$t_{1}^{2}+2t_{2}^{2}+t_{3}^{2}-t_{4}^{2}=2\varepsilon^{2}(x(P)^{2}-y(P)),$

so we see

$2\varepsilon^{2}|y(P)-x(P)^{2}|=\left|t_{1}^{2}+2t_{2}^{2}+t_{3}^{2}-t_{4}^{2}\right|.$

Next we apply the triangle inequality to get an expression to which we can
apply Equation 4 and the bound on
$|\left\llbracket\eta_{x,y}\right\rrbracket(Q)|$:

$\displaystyle 2\varepsilon^{2}|y(P)-x(P)^{2}|$
$\displaystyle=\left|t_{1}^{2}+2t_{2}^{2}+t_{3}^{2}-t_{4}^{2}\right|$
$\displaystyle=|t_{1}^{2}-f(t_{1})+2(t_{2}^{2}-f(t_{2}))+t_{3}^{2}-f(t_{3})-(t_{4}^{2}-f(t_{4}))$
$\displaystyle\quad\;+f(t_{1})+2f(t_{2})+f(t_{3})-f(t_{4})|$
$\displaystyle\leq|t_{1}^{2}-f(t_{1})|+2|t_{2}^{2}-f(t_{2})|+|t_{3}^{2}-f(t_{3})|+|t_{4}^{2}-f(t_{4})|$
$\displaystyle\quad\;+|f(t_{1})+2f(t_{2})+f(t_{3})-f(t_{4})|$
$\displaystyle=|t_{1}^{2}-f(t_{1})|+2|t_{2}^{2}-f(t_{2})|+|t_{3}^{2}-f(t_{3})|+|t_{4}^{2}-f(t_{4})|$
$\displaystyle\quad\;+|\left\llbracket\eta_{x,y}\right\rrbracket(Q)|$

Applying Equation 4 and the bound on
$|\left\llbracket\eta_{x,y}\right\rrbracket(Q)|$ yields

$\displaystyle 2\varepsilon^{2}|y(P)-x(P)^{2}|$
$\displaystyle\leq|t_{1}^{2}-f(t_{1})|+2|t_{2}^{2}-f(t_{2})|+|t_{3}^{2}-f(t_{3})|+|t_{4}^{2}-f(t_{4})|$
$\displaystyle\quad\;+|\left\llbracket\eta_{x,y}\right\rrbracket(Q)|$
$\displaystyle\leq\frac{1}{10}t_{1}^{3}+\frac{1}{5}t_{2}^{3}+\frac{1}{10}t_{3}^{3}+\frac{1}{10}t_{4}^{3}+6\varepsilon^{3}$

Finally we use that $t_{1}$, $t_{2}$ and $t_{3}$ are bounded in absolute value
by $\varepsilon$, and that $t_{4}$ is bounded by $2\varepsilon$:

$\displaystyle 2\varepsilon^{2}|y(P)-x(P)^{2}|$
$\displaystyle\leq\frac{1}{10}t_{1}^{3}+\frac{1}{5}t_{2}^{3}+\frac{1}{10}t_{3}^{3}+\frac{1}{10}t_{4}^{3}+6\varepsilon^{3}$
$\displaystyle\leq\frac{1}{10}\varepsilon^{3}+\frac{1}{5}\varepsilon^{3}+\frac{1}{10}\varepsilon^{3}+\frac{8}{10}\varepsilon^{3}+6\varepsilon^{3}$
$\displaystyle<200\varepsilon^{3}.$

So $|y(P)-x(P)^{2}|\leq 100\varepsilon$. This proves that $P\in
V(\Phi_{100\varepsilon})$, and therefore $V(\Phi)\neq\emptyset$.

This finishes the proof of the validity of the reduction of ETR-SQUARE-1 to
CE-EXPL. We conclude that for the given $f$, the problem CE-EXPL is
$\exists\mathbb{R}$-hard. ∎

###  2.3 Almost Square Explicit Inequality Constraints

In this section, we will prove a number of hardness results about the explicit
version of CCI. Before we can describe these results, we first need the
following definition:

######  Definition 19 (CCI-EXPL).

Let $f,g\colon U\to\mathbb{R}$ be two functions. Now we define the CCI-EXPL
problem to be the CCI problem corresponding to the functions
$f^{*},g^{*}\colon U^{2}\to\mathbb{R}$ defined by $f^{*}(x,y)=y-f(x)$ and
$g^{*}(x,y)=g(x)-y$.

We will prove that CCI-EXPL is $\exists\mathbb{R}$-hard in a large number
cases. In particular, we prove the following:

######  Corollary 20.

Let $U\subseteq\mathbb{R}$ be a neighborhood of $0$, and let $f,g\colon
U\to\mathbb{R}$ be functions which are 2 times differentiable such that
$f(0)=g(0)=0$ and
$f^{\prime}(0),f^{\prime\prime}(0),g^{\prime}(0),g^{\prime\prime}(0)\in\mathbb{Q}$
with $f^{\prime\prime}(0),g^{\prime\prime}(0)>0$. Now the problem CCI-EXPL is
$\exists\mathbb{R}$-hard, even when $\delta=O(n^{-c})$ for any constant $c>0$.

This corollary will be an important step towards proving Theorem 8. Before we
can prove this corollary, we first prove another result which is similar to
Lemma 18.

######  Lemma 21.

Let $U\subseteq\mathbb{R}$ be a neighborhood of 0, and let $f,g\colon
U\to\mathbb{R}$ be functions such that $|f(x)-x^{2}|\leq\frac{1}{10}|x|^{3}$
and $|g(x)-x^{2}|\leq\frac{1}{10}|x|^{3}$ for all $x\in U$. In this setting,
the problem CCI-EXPL is $\exists\mathbb{R}$-hard, even when $\delta=O(n^{-c})$
for any constant $c>0$.

###### Proof.

The idea is to use almost the same construction as in Lemma 18, so we
recommend the reader to first read the proof to this lemma. The the first main
difference is that some extra care needs to be taken when making the
constraints for the $\left\llbracket\delta_{i}\right\rrbracket$ variables.
Also the squaring constraints need to be handled in a slightly different way.
In order to do this, we replace the variables
$\left\llbracket\eta_{x,y}\right\rrbracket$ by two new variables
$\left\llbracket\eta_{x,y}^{\mathrm{low}}\right\rrbracket$ and
$\left\llbracket\eta_{x,y}^{\mathrm{high}}\right\rrbracket$, which impose a
lower bound, respectively upper bound, on the value of
$t_{1}^{2}+2t_{2}^{2}+t_{3}^{2}-t_{4}^{2}$. Here $t_{1}=\varepsilon$,
$t_{2}=\varepsilon x$, $t_{3}=\varepsilon y$ and
$t_{4}=\varepsilon+\varepsilon y$, as before.

#### Reduction.

Let $\Phi$ be an ETR-SQUARE-1 formula. We again pick any $\delta$ such that
$\delta<\frac{1}{4}$ and which satisfies any imposed requirement of the form
$\delta=O(n^{-c})$. We will construct a CCI-EXPL formula $\Psi$ such that
$V(\Phi)\neq\emptyset$ if and only if $V(\Psi)\neq\emptyset$. Let $M$ be the
constant obtained by applying Lemma 15 to $\Phi$, and let $L$ be a constant
such that $2^{-2^{L}}\leq\frac{1}{100}\cdot 2^{-2^{M}}$ and
$2^{-2^{L}}\leq\frac{1}{100}$, just like in the proof of Lemma 18.

We again introduce $\left\llbracket\delta_{i}\right\rrbracket$ for $0\leq
i\leq L$, where the variable $\left\llbracket\delta_{0}\right\rrbracket$
should satisfy the constraint
$\left\llbracket\delta_{0}\right\rrbracket=\delta$. For each $1\leq i\leq L$
we now add constraints enforcing

$\frac{1}{2}f(\left\llbracket\delta_{i-1}\right\rrbracket)\leq\left\llbracket\delta_{i}\right\rrbracket\leq
g(\left\llbracket\delta_{i-1}\right\rrbracket).$

Denote
$\left\llbracket\varepsilon\right\rrbracket=\left\llbracket\delta_{L}\right\rrbracket$.
The constraints $\left\llbracket\delta_{i}\right\rrbracket\leq
g(\left\llbracket\delta_{i-1}\right\rrbracket)$ are there to enforce that
$\left\llbracket\varepsilon\right\rrbracket\leq 2^{-2^{L}}$, and the
constraints
$\frac{1}{2}f(\left\llbracket\delta_{i-1}\right\rrbracket)\leq\left\llbracket\delta_{i}\right\rrbracket$
are there to enforce that $\varepsilon>0$.

We continue by defining variables $\left\llbracket\leq
g(\varepsilon)\right\rrbracket$ and $\left\llbracket\lesssim
2\varepsilon^{3}\right\rrbracket$ using constraints

$\displaystyle\left\llbracket\leq g(\varepsilon)\right\rrbracket$
$\displaystyle\leq g(\left\llbracket\varepsilon\right\rrbracket),$
$\displaystyle\left\llbracket\leq g(\varepsilon)\right\rrbracket$
$\displaystyle\geq 0,$ $\displaystyle\left\llbracket\lesssim
2\varepsilon^{3}\right\rrbracket$ $\displaystyle\leq
g(\left\llbracket\varepsilon\right\rrbracket+\left\llbracket\leq
g(\varepsilon)\right\rrbracket)-f(\left\llbracket\varepsilon\right\rrbracket),$
$\displaystyle\left\llbracket\lesssim 2\varepsilon^{3}\right\rrbracket$
$\displaystyle\geq 0.$

This new variable $\left\llbracket\lesssim 2\varepsilon^{3}\right\rrbracket$
is a replacement for the variable $\left\llbracket\approx
2\varepsilon^{3}\right\rrbracket$ which occurred in the proof of Lemma 18.
Later, we will show that $\left\llbracket\lesssim
2\varepsilon^{3}\right\rrbracket$ is upper bounded by $3\varepsilon^{3}$.

Next for each variable $x$ of $\Phi$, we add a variable
$\left\llbracket\varepsilon x\right\rrbracket$ to $\Psi$, with constraints
enforcing
$-\left\llbracket\varepsilon\right\rrbracket\leq\left\llbracket\varepsilon
x\right\rrbracket\leq\left\llbracket\varepsilon\right\rrbracket$. Constraints
of type $x+y=z$, type $x\geq 0$ or type $x=1$ are handled by replacing them by
constraints $\left\llbracket\varepsilon
x\right\rrbracket+\left\llbracket\varepsilon
y\right\rrbracket=\left\llbracket\varepsilon z\right\rrbracket$,
$\left\llbracket\varepsilon x\right\rrbracket\geq 0$ and
$\left\llbracket\varepsilon
x\right\rrbracket=\left\llbracket\varepsilon\right\rrbracket$, respectively.

For each constraint $y=x^{2}$, we introduce variables $\left\llbracket
t_{1}\right\rrbracket$, $\left\llbracket t_{2}\right\rrbracket$,
$\left\llbracket t_{3}\right\rrbracket$ and $\left\llbracket
t_{4}\right\rrbracket$ with constraints

$\displaystyle\left\llbracket t_{1}\right\rrbracket$
$\displaystyle=\left\llbracket\varepsilon\right\rrbracket,$
$\displaystyle\left\llbracket t_{2}\right\rrbracket$
$\displaystyle=\left\llbracket\varepsilon x\right\rrbracket,$
$\displaystyle\left\llbracket t_{3}\right\rrbracket$
$\displaystyle=\left\llbracket\varepsilon y\right\rrbracket,$
$\displaystyle\left\llbracket t_{4}\right\rrbracket$
$\displaystyle=\left\llbracket\varepsilon\right\rrbracket+\left\llbracket\varepsilon
y\right\rrbracket.$

Next we introduce two new variables:
$\left\llbracket\eta_{x,y}^{\mathrm{low}}\right\rrbracket$ and
$\left\llbracket\eta_{x,y}^{\mathrm{high}}\right\rrbracket$, together with
constraints enforcing

$\displaystyle\left\llbracket\eta_{x,y}^{\mathrm{low}}\right\rrbracket$
$\displaystyle\leq g(\left\llbracket t_{1}\right\rrbracket)+2g(\left\llbracket
t_{2}\right\rrbracket)+g(\left\llbracket
t_{3}\right\rrbracket)-f(\left\llbracket t_{4}\right\rrbracket),$
$\displaystyle\left\llbracket\eta_{x,y}^{\mathrm{high}}\right\rrbracket$
$\displaystyle\geq f(\left\llbracket t_{1}\right\rrbracket)+2f(\left\llbracket
t_{2}\right\rrbracket)+f(\left\llbracket
t_{3}\right\rrbracket)-g(\left\llbracket t_{4}\right\rrbracket),$
$\displaystyle\left\llbracket\eta_{x,y}^{\mathrm{low}}\right\rrbracket$
$\displaystyle\geq-2\left\llbracket\lesssim 2\varepsilon^{3}\right\rrbracket,$
$\displaystyle\left\llbracket\eta_{x,y}^{\mathrm{high}}\right\rrbracket$
$\displaystyle\leq 2\left\llbracket\lesssim 2\varepsilon^{3}\right\rrbracket.$

Note that the variables
$\left\llbracket\eta_{x,y}^{\mathrm{low}}\right\rrbracket$ and
$\left\llbracket\eta_{x,y}^{\mathrm{high}}\right\rrbracket$ are not completely
necessary, and that it is also possible to use direct constraints

$\displaystyle-2\left\llbracket\lesssim 2\varepsilon^{3}\right\rrbracket$
$\displaystyle\leq g(\left\llbracket t_{1}\right\rrbracket)+2g(\left\llbracket
t_{2}\right\rrbracket)+g(\left\llbracket
t_{3}\right\rrbracket)-f(\left\llbracket t_{4}\right\rrbracket),$
$\displaystyle 2\left\llbracket\lesssim 2\varepsilon^{3}\right\rrbracket$
$\displaystyle\geq f(\left\llbracket t_{1}\right\rrbracket)+2f(\left\llbracket
t_{2}\right\rrbracket)+f(\left\llbracket
t_{3}\right\rrbracket)-g(\left\llbracket t_{4}\right\rrbracket)$

instead. The two variables
$\left\llbracket\eta_{x,y}^{\mathrm{low}}\right\rrbracket$ and
$\left\llbracket\eta_{x,y}^{\mathrm{high}}\right\rrbracket$ are included since
these slightly simplify the notation when proving correctness of this
construction later on. This completes the construction of $\Psi$, which can be
performed in linear time.

#### Calculations.

Let $\varepsilon$ be any real number such that there exist reals $\delta_{i}$
for $0\leq i\leq L$ satisfying $\delta_{0}=\delta$, $\delta_{L}=\varepsilon$
and $\frac{1}{2}f(\delta_{i-1})\leq\delta_{i}\leq g(\delta_{i-1})$ for all
$1\leq i\leq L$. Now we have the following facts (these facts hold in
particular if $\varepsilon=\left\llbracket\varepsilon\right\rrbracket(Q)$ for
some $Q\in V(\Psi)$):

$\displaystyle|f(x)-x^{2}|$ $\displaystyle\leq\frac{1}{10}|x|^{3}$
$\displaystyle\text{for }x\in[-\delta,\delta],$ (9)
$\displaystyle|g(x)-x^{2}|$ $\displaystyle\leq\frac{1}{10}|x|^{3}$
$\displaystyle\text{for }x\in[-\delta,\delta],$ (10)
$\displaystyle\frac{1}{2}f(x)$ $\displaystyle\leq g(x)$
$\displaystyle\text{for }x\in[-\delta,\delta],$ (11)
$\displaystyle\varepsilon$
$\displaystyle\leq\frac{1}{100}\min\left(2^{-2^{M}},\delta\right),$ (12)
$\displaystyle f(\varepsilon)$ $\displaystyle<\varepsilon,\quad
g(\varepsilon)<\varepsilon,$ (13) $\displaystyle\left\llbracket\lesssim
2\varepsilon^{3}\right\rrbracket(Q)$ $\displaystyle\leq
3\left\llbracket\varepsilon\right\rrbracket(Q)^{3}$ $\displaystyle\text{for
}Q\in V(\Psi),$ (14) $\displaystyle
g(\varepsilon+g(\varepsilon))-f(\varepsilon)$
$\displaystyle\geq\varepsilon^{3}.$ (15)

Equations 9 and 10 are assumptions from the statement of the lemma. Equation
11 follows from this, together with the fact that $|x|$ is bounded by
$\frac{1}{4}$:

$\frac{1}{2}f(x)\leq\frac{1}{2}x^{2}+\frac{1}{20}|x|^{3}\leq
x^{2}-\frac{1}{10}|x|^{3}\leq g(x).$

Equation 12 can be derived in the same way as Equation 6 from Lemma 18, and
now Equation 13 follows from this with Equations 9 and 10.

In order to derive Equation 14, we use the definition of the variable
$\left\llbracket\lesssim 2\varepsilon^{3}\right\rrbracket$ and apply Equations
9 and 10 to this (here we take
$\varepsilon=\left\llbracket\varepsilon\right\rrbracket(Q)$ to simplify the
notation a bit):

$\displaystyle\left\llbracket\lesssim 2\varepsilon^{3}\right\rrbracket(Q)$
$\displaystyle\leq g(\varepsilon+\left\llbracket\leq
g(\varepsilon)\right\rrbracket(Q))-f(\varepsilon)$
$\displaystyle\leq(\varepsilon+\left\llbracket\leq
g(\varepsilon)\right\rrbracket(Q))^{2}+\frac{1}{10}(\varepsilon+\left\llbracket\leq
g(\varepsilon)\right\rrbracket(Q))^{3}-\varepsilon^{2}+\frac{1}{10}\varepsilon^{3}.$

Combining this with the constraint $\left\llbracket\leq
g(\varepsilon)\right\rrbracket\leq
g(\left\llbracket\varepsilon\right\rrbracket)$ and Equations 10 and 13, we get

$\displaystyle\left\llbracket\lesssim 2\varepsilon^{3}\right\rrbracket(Q)$
$\displaystyle\leq(\varepsilon+\left\llbracket\leq
g(\varepsilon)\right\rrbracket(Q))^{2}+\frac{1}{10}(\varepsilon+\left\llbracket\leq
g(\varepsilon)\right\rrbracket(Q))^{3}-\varepsilon^{2}+\frac{1}{10}\varepsilon^{3}$
$\displaystyle\leq(\varepsilon+g(\varepsilon))^{2}+\frac{1}{10}(\varepsilon+g(\varepsilon))^{3}-\varepsilon^{2}+\frac{1}{10}\varepsilon^{3}$
$\displaystyle\leq\left(\varepsilon+\varepsilon^{2}+\frac{1}{10}\varepsilon^{3}\right)^{2}+\frac{1}{10}\left(\varepsilon+\varepsilon\right)^{3}-\varepsilon^{2}+\frac{1}{10}\varepsilon^{3}$
$\displaystyle=\frac{29}{10}\varepsilon^{3}+\frac{6}{5}\varepsilon^{4}+\frac{1}{5}\varepsilon^{5}+\frac{1}{100}\varepsilon^{6}.$

Combining this with $\varepsilon\leq\frac{1}{100}$ (which follows from
Equation 12) yields that $\left\llbracket\lesssim
2\varepsilon^{3}\right\rrbracket(Q)\leq 3\varepsilon^{3}$, as we wanted.

Finally Equation 15 follows from Equations 9, 10 and 13 in the following
manner:

$\displaystyle g(\varepsilon+g(\varepsilon))-f(\varepsilon)$
$\displaystyle\geq(\varepsilon+g(\varepsilon))^{2}-\frac{1}{10}(\varepsilon+g(\varepsilon))^{3}-\varepsilon^{2}-\frac{1}{10}\varepsilon^{3}$
$\displaystyle\geq\left(\varepsilon+\varepsilon^{2}-\frac{1}{10}\varepsilon^{3}\right)^{2}-\frac{1}{10}(\varepsilon+\varepsilon)^{3}-\varepsilon^{2}-\frac{1}{10}\varepsilon^{3}$
$\displaystyle=\frac{11}{10}\varepsilon^{3}+\frac{4}{5}\varepsilon^{4}-\frac{1}{5}\varepsilon^{5}+\frac{1}{100}\varepsilon^{6}$
$\displaystyle\geq\varepsilon^{3}.$

####  $V(\Phi)$ nonempty implies $V(\Psi)$ nonempty.

Suppose that $V(\Phi)\neq\emptyset$, so there exists some $P\in V(\Phi)$. We
want to show that also $V(\Psi)\neq\emptyset$, to do this we construct a point
$Q\in V(\Psi)$. We start by taking
$\left\llbracket\delta_{0}\right\rrbracket(Q)=\delta$ and
$\left\llbracket\delta_{i}\right\rrbracket(Q)=g(\left\llbracket\delta_{i-1}\right\rrbracket)$
for all $1\leq i\leq L$. By Equation 11, this definition satisfies all
constraints on the $\left\llbracket\delta_{i}\right\rrbracket$. Denote
$\varepsilon=\left\llbracket\varepsilon\right\rrbracket(Q)=\left\llbracket\delta_{L}\right\rrbracket(Q)$.
Next we take $\left\llbracket\leq
g(\varepsilon)\right\rrbracket(Q)=g(\varepsilon)$ and $\left\llbracket\lesssim
2\varepsilon^{3}\right\rrbracket(Q)=g(\varepsilon+g(\varepsilon))-f(\varepsilon)$,
so by Equation 15 we know that $\left\llbracket\lesssim
2\varepsilon^{3}\right\rrbracket(Q)\geq\varepsilon^{3}$.

For all variables $x$ of $\Phi$, we take $\left\llbracket\varepsilon
x\right\rrbracket(Q)=\varepsilon x(P)$. Since $V(P)\subseteq[-1,1]^{n}$, it
follows that all inequalities of the form
$-\left\llbracket\varepsilon\right\rrbracket(Q)\leq\left\llbracket\varepsilon
x\right\rrbracket(Q)\leq\left\llbracket\varepsilon\right\rrbracket(Q)$ are
satisfied in this way. Also for every constraint from $\Phi$ of one of the
forms $x+y=z$, $x\geq 0$ or $x=1$, the corresponding constraint in $\Psi$ is
clearly satisfied.

Next we consider a squaring constraint $y=x^{2}$ from $\Phi$, for each such
constraint we take

$\displaystyle\left\llbracket t_{1}\right\rrbracket(Q)$
$\displaystyle=\varepsilon,$ $\displaystyle\left\llbracket
t_{2}\right\rrbracket(Q)$ $\displaystyle=\left\llbracket\varepsilon
x\right\rrbracket(Q),$ $\displaystyle\left\llbracket t_{3}\right\rrbracket(Q)$
$\displaystyle=\left\llbracket\varepsilon y\right\rrbracket(Q),$
$\displaystyle\left\llbracket t_{4}\right\rrbracket(Q)$
$\displaystyle=\varepsilon+\left\llbracket\varepsilon y\right\rrbracket(Q),$
$\displaystyle\left\llbracket\eta_{x,y}^{\mathrm{low}}\right\rrbracket(Q)$
$\displaystyle=g(\left\llbracket t_{1}\right\rrbracket(Q))+2g(\left\llbracket
t_{2}\right\rrbracket(Q))+g(\left\llbracket
t_{3}\right\rrbracket(Q))-f(\left\llbracket t_{4}\right\rrbracket(Q)),$
$\displaystyle\left\llbracket\eta_{x,y}^{\mathrm{high}}\right\rrbracket(Q)$
$\displaystyle=f(\left\llbracket t_{1}\right\rrbracket(Q))+2f(\left\llbracket
t_{2}\right\rrbracket(Q))+f(\left\llbracket
t_{3}\right\rrbracket(Q))-g(\left\llbracket t_{4}\right\rrbracket(Q)).$

Using these definitions, the only constraints for which we still need to check
whether $Q$ satisfies them, are the constraints of the form
$\left\llbracket\eta_{x,y}^{\mathrm{low}}\right\rrbracket\geq-2\left\llbracket\lesssim
2\varepsilon^{3}\right\rrbracket$ and
$\left\llbracket\eta_{x,y}^{\mathrm{high}}\right\rrbracket\leq
2\left\llbracket\lesssim 2\varepsilon^{3}\right\rrbracket$.

We start by checking the first of these constraints. Denote
$t_{1}=\left\llbracket t_{1}\right\rrbracket(Q)$, $t_{2}=\left\llbracket
t_{2}\right\rrbracket(Q)$, $t_{3}=\left\llbracket t_{3}\right\rrbracket(Q)$
and $t_{4}=\left\llbracket t_{4}\right\rrbracket(Q)$. Now we can apply
Equations 9 and 10 to the definition of
$\left\llbracket\eta_{x,y}^{\mathrm{low}}\right\rrbracket$:

$\displaystyle\left\llbracket\eta_{x,y}^{\mathrm{low}}\right\rrbracket(Q)$
$\displaystyle=g(t_{1})+2g(t_{2})+g(t_{3})-f(t_{4})$ $\displaystyle\geq
t_{1}^{2}-\frac{1}{10}|t_{1}|^{3}+2t_{2}^{2}-\frac{1}{5}|t_{2}|^{3}+t_{3}^{2}-\frac{1}{10}|t_{3}|^{3}-t_{4}^{2}-\frac{1}{10}|t_{4}|^{3}$
$\displaystyle=t_{1}^{2}+2t_{2}^{2}+t_{3}^{2}-t_{4}^{2}-\left(\frac{1}{10}|t_{1}|^{3}+\frac{1}{5}|t_{2}|^{3}+\frac{1}{10}|t_{3}|^{3}+\frac{1}{10}|t_{4}|^{3}\right).$

Since $t_{1},\ldots t_{4}$ were chosen such that
$t_{1}^{2}+2t_{2}^{2}+t_{3}^{2}-t_{4}^{2}=\varepsilon^{2}x(P)^{2}-\varepsilon^{2}y(P)$,
and by the fact that $y(P)=x(P)^{2}$, it follows that
$t_{1}^{2}+2t_{2}^{2}+t_{3}^{2}-t_{4}^{2}=0$. Furthermore, $t_{1}$, $t_{2}$
and $t_{3}$ are all bounded by $\varepsilon$ in absolute value, while
$|t_{4}|$ is bounded by $2\varepsilon$. This yields

$\displaystyle\left\llbracket\eta_{x,y}^{\mathrm{low}}\right\rrbracket(Q)$
$\displaystyle\geq
t_{1}^{2}+2t_{2}^{2}+t_{3}^{2}-t_{4}^{2}-\left(\frac{1}{10}|t_{1}|^{3}+\frac{1}{5}|t_{2}|^{3}+\frac{1}{10}|t_{3}|^{3}+\frac{1}{10}|t_{4}|^{3}\right)$
$\displaystyle\geq
0-\left(\frac{1}{10}\varepsilon^{3}+\frac{1}{5}\varepsilon^{3}+\frac{1}{10}\varepsilon^{3}+\frac{8}{10}\varepsilon^{3}\right)$
$\displaystyle\geq-2\varepsilon^{3}.$

Combining this with $\left\llbracket\lesssim
2\varepsilon^{3}\right\rrbracket(Q)\geq\varepsilon^{3}$, we find
$\left\llbracket\eta_{x,y}^{\mathrm{low}}\right\rrbracket(Q)\geq-2\left\llbracket\lesssim
2\varepsilon^{3}\right\rrbracket(Q)$.

Next we consider the constraint
$\left\llbracket\eta_{x,y}^{\mathrm{high}}\right\rrbracket\leq
2\left\llbracket\lesssim 2\varepsilon^{3}\right\rrbracket$. We apply Equations
9 and 10 to the definition of
$\left\llbracket\eta_{x,y}^{\mathrm{high}}\right\rrbracket$:

$\displaystyle\left\llbracket\eta_{x,y}^{\mathrm{high}}\right\rrbracket(Q)$
$\displaystyle=f(t_{1})+2f(t_{2})+f(t_{3})-g(t_{4})$ $\displaystyle\leq
t_{1}^{2}+\frac{1}{10}|t_{1}|^{3}+2t_{2}^{2}+\frac{1}{5}|t_{2}|^{3}+t_{3}^{2}+\frac{1}{10}|t_{3}|^{3}-t_{4}^{2}+\frac{1}{10}|t_{4}|^{3}$
$\displaystyle=t_{1}^{2}+2t_{2}^{2}+t_{3}^{2}-t_{4}^{2}+\frac{1}{10}|t_{1}|^{3}+\frac{1}{5}|t_{2}|^{3}+\frac{1}{10}|t_{3}|^{3}+\frac{1}{10}|t_{4}|^{3}.$

Here we can apply that $t_{1}^{2}+2t_{2}^{2}+t_{3}^{2}-t_{4}^{2}=0$, and that
$|t_{1}|$, $|t_{2}|$ and $|t_{3}|$ are bounded by $\varepsilon$ and $|t_{4}|$
is bounded by $2\varepsilon$ to get

$\displaystyle\left\llbracket\eta_{x,y}^{\mathrm{high}}\right\rrbracket(Q)$
$\displaystyle\leq
t_{1}^{2}+2t_{2}^{2}+t_{3}^{2}-t_{4}^{2}+\frac{1}{10}|t_{1}|^{3}+\frac{1}{5}|t_{2}|^{3}+\frac{1}{10}|t_{3}|^{3}+\frac{1}{10}|t_{4}|^{3}$
$\displaystyle\leq
0+\frac{1}{10}\varepsilon^{3}+\frac{1}{5}\varepsilon^{3}+\frac{1}{10}\varepsilon^{3}+\frac{8}{10}\varepsilon^{3}$
$\displaystyle\leq 2\varepsilon^{3}.$

So we get that
$\left\llbracket\eta_{x,y}^{\mathrm{high}}\right\rrbracket(Q)\leq
2\left\llbracket\lesssim 2\varepsilon^{3}\right\rrbracket(Q)$.

We conclude that $Q$ satisfies all constraints from $\Psi$, and therefore
$Q\in V(\Psi)$. This proves that $V(\Psi)\neq\emptyset$.

####  $V(\Psi)$ nonempty implies $V(\Phi)$ nonempty.

Next, let $Q\in V(\Psi)$. Just as in the proof of Lemma 18, we want to show
that $|x(Q)|\leq\delta$ for all variables $x$ of $\Psi$, and we want to prove
that $V(\Phi)\neq\emptyset$. Bounding the coordinates goes in exactly the same
way as in Lemma 18.

To show that $V(\Phi)\neq\emptyset$, we again use Lemma 15, we construct a
point $P$ in $V(\Phi_{100\varepsilon})$, where we again denote
$\varepsilon=\left\llbracket\varepsilon\right\rrbracket(Q)$. This would imply
$V(\Phi)\neq\emptyset$ since $100\varepsilon\leq 2^{-2^{M}}$. We take
$x(P)=\frac{\left\llbracket\varepsilon x\right\rrbracket(Q)}{\varepsilon}$ for
all variables $x$ of $\Phi$. Now $P$ satisfies all linear constraints and
inequality constraints of $\Phi$, it only remains to be checked that it
satisfies the constraints $|y-x^{2}|\leq 100\varepsilon$ of
$\Phi_{100\varepsilon}$.

We start by proving that $x(P)^{2}-y(P)\leq 100\varepsilon$. Denote
$t_{1}=\left\llbracket t_{1}\right\rrbracket(Q)=\varepsilon$,
$t_{2}=\left\llbracket t_{2}\right\rrbracket(Q)=\varepsilon x(P)$,
$t_{3}=\left\llbracket t_{3}\right\rrbracket(Q)=\varepsilon y(P)$ and
$t_{4}=\left\llbracket t_{4}\right\rrbracket(Q)=\varepsilon+\varepsilon y(P)$.
We have that

$t_{1}^{2}+2t_{2}^{2}+t_{3}^{2}-t_{4}^{2}=2\varepsilon^{2}(x(P)^{2}-y(P)).$

Note that from Equations 9 and 10 it also follows that $x^{2}\leq
f(x)+\frac{1}{10}|x|^{3}$ and $x^{2}\geq g(x)-\frac{1}{10}|x|^{3}$ for all
$x\in[-\delta,\delta]$. Using this, we find

$\displaystyle 2\varepsilon^{2}(x(P)^{2}-y(P))$
$\displaystyle=t_{1}^{2}+2t_{2}^{2}+t_{3}^{2}-t_{4}^{2}$ $\displaystyle\leq
f(t_{1})+\frac{1}{10}|t_{1}|^{3}+2f(t_{2})+\frac{1}{5}|t_{2}|^{3}$
$\displaystyle\quad+f(t_{3})+\frac{1}{10}|t_{3}|^{3}-g(t_{4})+\frac{1}{10}|t_{4}|^{3}$
$\displaystyle=f(t_{1})+2f(t_{2})+f(t_{3})-g(t_{4})$
$\displaystyle\quad+\frac{1}{10}|t_{1}|^{3}+\frac{1}{5}|t_{2}|^{3}+\frac{1}{10}|t_{3}|^{3}+\frac{1}{10}|t_{4}|^{3}.$

To bound this, we use the variable
$\left\llbracket\eta_{x,y}^{\mathrm{high}}\right\rrbracket$, and the
observation that $t_{1}$, $t_{2}$ and $t_{3}$ are bounded in absolute value by
$\varepsilon$, and $|t_{4}|$ is bounded by $2\varepsilon$:

$\displaystyle 2\varepsilon^{2}(x(P)^{2}-y(P))$ $\displaystyle\leq
f(t_{1})+2f(t_{2})+f(t_{3})-g(t_{4})$
$\displaystyle\quad+\frac{1}{10}|t_{1}|^{3}+\frac{1}{5}|t_{2}|^{3}+\frac{1}{10}|t_{3}|^{3}+\frac{1}{10}|t_{4}|^{3}$
$\displaystyle\leq\left\llbracket\eta_{x,y}^{\mathrm{high}}\right\rrbracket(Q)+\frac{1}{10}\varepsilon^{3}+\frac{1}{5}\varepsilon^{3}+\frac{1}{10}\varepsilon^{3}+\frac{8}{10}\varepsilon^{3}$
$\displaystyle\leq 2\left\llbracket\lesssim
2\varepsilon^{3}\right\rrbracket(Q)+2\varepsilon^{3}.$

Here we can apply Equation 14 to find

$2\varepsilon^{2}(x(P)^{2}-y(P))\leq 8\varepsilon^{3}<200\varepsilon^{3}.$

This implies $x(P)^{2}-y(P)\leq 100\varepsilon$, as we wanted.

The proof that $x(P)^{2}-y(P)\geq-100\varepsilon$ works in a similar manner.
Leaving out some intermediate steps, it looks as follows:

$\displaystyle 2\varepsilon^{2}(x(P)^{2}-y(P))$
$\displaystyle=t_{1}^{2}+2t_{2}^{2}+t_{3}^{2}-t_{4}^{2}$ $\displaystyle\geq
g(t_{1})+2g(t_{2})+g(t_{3})-f(t_{4})$
$\displaystyle\quad-\left(\frac{1}{10}|t_{1}|^{3}+\frac{1}{5}|t_{2}|^{3}+\frac{1}{10}|t_{3}|^{3}+\frac{1}{10}|t_{4}|^{3}\right)$
$\displaystyle\geq\left\llbracket\eta_{x,y}^{\mathrm{low}}\right\rrbracket(Q)-2\varepsilon^{3}$
$\displaystyle\geq-8\varepsilon^{3}>-200\varepsilon^{3},$

and therefore $x(P)^{2}-y(P)\geq-100\varepsilon$. This implies that $P\in
V(\Phi_{100\varepsilon})$, and therefore $V(\Phi)\neq\emptyset$.

This completes the proof of the validity of the reduction of ETR-SQUARE-1 to
CCI-EXPL. So for $f$ and $g$ satisfying the conditions from the lemma, the
problem CCI-EXPL is $\exists\mathbb{R}$-hard. ∎

Now that hardness of this restricted version of CCI-EXPL is proven, this
result can be generalized in small steps until finally Theorem 10 is proven.

Before we do this, we first note that in any CCI-EXPL formula, constraints of
the form $x=q\cdot y$, where $x,y$ are variables and $q$ is a rational
constant, can be enforced using a constant number of addition constraints and
new variables. To illustrate this, we will discuss the case where $q\in[0,1]$
here. Other cases can be handled in a similar manner. Assume that $q=a/b$ for
a positive integer $b$ and an integer $0\leq a\leq b$. Now we can introduce
variables $\left\llbracket\frac{i}{b}y\right\rrbracket$ for all $0\leq i\leq
b$, which satisfy constraints

$\displaystyle\left\llbracket\frac{0}{b}y\right\rrbracket$
$\displaystyle=\left\llbracket\frac{0}{b}y\right\rrbracket+\left\llbracket\frac{0}{b}y\right\rrbracket,$
$\displaystyle\left\llbracket\frac{i+1}{b}y\right\rrbracket$
$\displaystyle=\left\llbracket\frac{i}{b}y\right\rrbracket+\left\llbracket\frac{1}{b}y\right\rrbracket$
$\displaystyle\text{for }0\leq i<b,$
$\displaystyle\left\llbracket\frac{b}{b}y\right\rrbracket$
$\displaystyle=\left\llbracket\frac{0}{b}y\right\rrbracket+y,$
$\displaystyle\left\llbracket\frac{a}{b}y\right\rrbracket$
$\displaystyle=\left\llbracket\frac{0}{b}y\right\rrbracket+x.$

This exactly enforces that $x=\frac{a}{b}\cdot y$.

Now the next step when working towards Theorem 10, is to slightly relax the
constraints on $f$ and $g$, by allowing the difference with squaring to be any
$O(x^{3})$ function, instead of just functions bounded by
$\frac{1}{10}|x|^{3}$ in absolute value.

######  Lemma 22.

Let $U\subseteq\mathbb{R}$ be a neighborhood of 0, and let $f,g\colon
U\to\mathbb{R}$ be functions such that $f(x)=x^{2}+O(x^{3})$ and
$g(x)=x^{2}+O(x^{3})$ as $x\to 0$. Now the problem CCI-EXPL is
$\exists\mathbb{R}$-hard, even when $\delta=O(n^{-c})$ for any constant $c>0$.

###### Proof.

Let $c$ be a constant such that $|f(x)-x^{2}|\leq c|x|^{3}$ and
$|g(x)-x^{2}|\leq c|x|^{3}$ for all $x\in U^{\prime}$ where
$U^{\prime}\subseteq U$ is a neighborhood of $0$. Now let $N$ be a positive
integer larger than $10c$. This implies that for all $x\in U^{\prime}$

$\displaystyle|N^{2}f(x/N)-x^{2}|$ $\displaystyle\leq\frac{1}{10}|x|^{3}\text{
and}$ $\displaystyle|N^{2}g(x/N)-x^{2}|$
$\displaystyle\leq\frac{1}{10}|x|^{3}.$

If we define $f^{*}$ and $g^{*}$ by $f^{*}(x)=N^{2}f(x/N)$ and
$g^{*}(x)=N^{2}g(x/N)$, then using Lemma 21, we get that the problem CCI-EXPL
is $\exists\mathbb{R}$-hard for $f^{*}$ and $g^{*}$. For the rest of the proof
of this lemma, we will denote this specific CCI-EXPL version by $\textrm{CCI-
EXPL}^{*}$.

We give a reduction from $\textrm{CCI-EXPL}^{*}$ to the CCI-EXPL version with
$f$ and $g$. Let $(\delta,\Phi)$ be a $\textrm{CCI-EXPL}^{*}$ instance. Now
for every variable $x$ in this instance, we add extra variables
$\left\llbracket x/N\right\rrbracket$, $\left\llbracket
x/N^{2}\right\rrbracket$ and we add constraints enforcing

$\displaystyle\left\llbracket\frac{x}{N}\right\rrbracket$
$\displaystyle=\frac{\left\llbracket x\right\rrbracket}{N},$
$\displaystyle\left\llbracket\frac{x}{N^{2}}\right\rrbracket$
$\displaystyle=\frac{\left\llbracket x\right\rrbracket}{N^{2}}.$

Next we replace every constraint of the form $y\geq f^{*}(x)$ by a constraint
$\left\llbracket y/N^{2}\right\rrbracket\geq f(\left\llbracket
x/N\right\rrbracket)$, and we replace every constraint of the form $y\leq
g^{*}(x)$ by a constraint $\left\llbracket y/N^{2}\right\rrbracket\leq
g(\left\llbracket x/N\right\rrbracket)$. This results in a CCI formula which
has a solution exactly when $\Phi$ has one, and furthermore for all possible
solutions all variables can be seen to be bounded in absolute value by
$\delta$. This whole reduction only takes linear time. ∎

In the next lemma, we allow even more possible $f$ and $g$.

######  Lemma 23.

Let $U\subseteq\mathbb{R}$ be a neighborhood of $0$, and let $f,g\colon
U\to\mathbb{R}$ be functions such that $f(x)=ax+bx^{2}+O(x^{3})$ and
$g(x)=cx+dx^{2}+O(x^{3})$ as $x\to 0$, where $a,b,c,d\in\mathbb{Q}$ and
$b,d>0$. Now the problem CCI-EXPL is $\exists\mathbb{R}$-hard, even when
$\delta=O(n^{-c})$ for any constant $c>0$.

###### Proof.

We define $f^{*}$ and $g^{*}$ as $f*(x)=(f(x)-ax)/b$ and $g*(x)=(g(x)-cx)/d$.
From the constraints on $f$ and $g$ it follows that $f^{*}(x)=x^{2}+O(x^{3})$
and $g^{*}(x)=x^{2}+O(x^{3})$. Therefore we can apply the previous lemma to
these functions to find that the CCI-EXPL problem with $f^{*}$ and $g^{*}$ is
$\exists\mathbb{R}$-hard. We will denote this problem by $\textrm{CCI-
EXPL}^{*}$, and give a reduction from $\textrm{CCI-EXPL}^{*}$ to the CCI-EXPL
problem with $f$ and $g$ as defined in the lemma statement.

Let $(\delta,\Phi)$ be any instance of $\textrm{CCI-EXPL}^{*}$. We denote

$\delta^{\prime}=(1+|a|+|b|+|c|+|d|)\delta.$

Now we build an instance $(\delta^{\prime},\Psi)$ of CCI-EXPL in the following
manner: We start by adding a variable $\left\llbracket\delta\right\rrbracket$
which is meant as a replacement for the $\delta$ in conditions of the form
$x=\delta$ in $\Phi$. To introduce this variable, we introduce an auxiliary
variable $\left\llbracket\delta^{\prime}\right\rrbracket$ and enforce the
following constraints:

$\displaystyle\left\llbracket\delta^{\prime}\right\rrbracket$
$\displaystyle=\delta^{\prime},$
$\displaystyle\left\llbracket\delta^{\prime}\right\rrbracket$
$\displaystyle=(1+|a|+|b|+|c|+|d|)\left\llbracket\delta\right\rrbracket.$

We also add every variable of $\Phi$ and all constraints of the form $x+y=z$
or $x\geq 0$ from $\Phi$ to $\Psi$, and for every constraint $x=\delta$ in
$\Phi$ we add a constraint $x=\left\llbracket\delta\right\rrbracket$ to
$\Psi$.

For every constraint $y\geq f^{*}(x)$ of $\Phi$ we introduce a new variable
$\left\llbracket ax+by\right\rrbracket$ to $\Psi$ which we force to equal
$ax+by$ using some linear constraints. Furthermore we add a constraint
$\left\llbracket ax+by\right\rrbracket\geq f(x)$. For constraints of the form
$y\leq g^{*}(x)$ we do something similar.

In this way, $(\delta^{\prime},\Psi)$ is a valid CCI-EXPL instance since all
values of the variables in any solutions can be seen to be bounded by
$\delta^{\prime}$ using the triangle inequality. Furthermore, the new instance
$\Psi$ differs from $\Phi$ only by new auxiliary variables, and otherwise has
exactly the same constraints on the original variables. Thus $V(\Psi)$ is non-
empty if and only if $V(\Phi)$ is nonempty. ∎

The next step is to notice that any function which is 2 times differentiable
with nonzero second derivative satisfies the constraints from the previous
lemma. This leads to the following result:

See 20

###### Proof.

Using Taylor’s theorem, we find that

$\displaystyle f(x)$
$\displaystyle=f^{\prime}(0)x+\frac{f^{\prime\prime}(0)}{2}x^{2}+O(x^{3})\text{
and}$ $\displaystyle g(x)$
$\displaystyle=g^{\prime}(0)x+\frac{g^{\prime\prime}(0)}{2}x^{2}+O(x^{3}).$

To this we can apply the previous lemma to find that CCI-EXPL is
$\exists\mathbb{R}$-hard, even when $\delta=O(n^{-c})$ for any constant $c>0$.
∎

###  2.4 Implicit Constraints

Using, Corollary 20 we will show Theorem 10 and Theorem 8 in this order. The
next lemma is almost equivalent to Theorem 10. The only difference is that the
conditions $f_{y}(0,0)>0$ and $g_{y}(0,0)<0$ are added.

######  Lemma 24.

Let $f,g\colon U^{2}\to\mathbb{R}$ be two functions, with $f$ well-behaved and
convexly curved, and $g$ well-behaved and concavely curved. Furthermore assume
that their partial derivatives satisfy $f_{y}(0,0)>0$ and $g_{y}(0,0)<0$. Then
the CCI problem is $\exists\mathbb{R}$-hard, even when $\delta=O(n^{-c})$ for
any constant $c>0$.

###### Proof.

Using the implicit function theorem, we find that in a neighborhood
$(U^{\prime})^{2}\subseteq U^{2}$ of $(0,0)$, the curve $f(x,y)=0$ can also be
given in an explicit form $y=f_{\textrm{expl}}(x)$, where $f_{\textrm{expl}}$
is some $C^{2}$-function $U^{\prime}\to\mathbb{R}$. So for
$(x,y)\in(U^{\prime})^{2}$ we have $f(x,y)=0$ if and only if
$y=f_{\textrm{expl}}(x)$. Since $f_{y}(0,0)>0$, it also follows that
$f(x,y)\geq 0$ if and only if $y\geq f_{\textrm{expl}}(x)$. Furthermore, the
implicit function theorem also states that the derivative of
$f_{\textrm{expl}}$ is given by

$f_{\textrm{expl}}^{\prime}(x)=\frac{f_{x}(x,f_{\textrm{expl}}^{\prime}(x))}{f_{y}(x,f_{\textrm{expl}}^{\prime}(x))}.$

From this it can be computed that the second derivative in 0 is

$f_{\textrm{expl}}^{\prime\prime}(0)=-\left(\frac{f_{y}^{2}f_{xx}-2f_{x}f_{y}f_{xy}+f_{x}^{2}f_{yy}}{f_{y}^{3}}\right)(0,0).$

Note that the fact that $f$ is convexly curved exactly implies that the
numerator of this expression is a positive number. Using the assumptions from
the lemma statement, we conclude that $f_{\textrm{expl}}^{\prime\prime}(0)$ is
a positive rational number.

In a analogous way, we can write the condition $g(x,y)\geq 0$ in the form
$y\leq g_{\textrm{expl}}(x)$ in some neighborhood of $(0,0)$, where
$g_{\textrm{expl}}$ is a $C^{2}$-function with rational first and second
derivative in $0$, and with positive second derivative.

We conclude that the problem CCI is equivalent to the problem CCI-EXPL for
$f_{\textrm{expl}}$ and $g_{\textrm{expl}}$, and by the Corollary 20 this
problem is $\exists\mathbb{R}$-hard. ∎

From here it is a small step to prove the main result:

See 10

###### Proof.

Without loss of generality, we may assume that $f_{y}(0,0)\neq 0$ and
$g_{y}(0,0)\neq 0$. In any other case, we can just interchange the variables
in one of the functions.

In the case where $f_{y}(0,0)>0$ and $g_{y}(0,0)<0$, we can apply the previous
lemma and we are done. For the case $f_{y}(0,0)<0$ and $g_{y}(0,0)<0$, we can
provide a reduction from CCI with functions $f^{*}(x,y)=f(-x,-y)$ and
$g^{*}(x,y)=g(x,y)$. For the case $f_{y}(0,0)>0$ and $g_{y}(0,0)>0$ we can
make a reduction from CCI with functions $f^{*}(x,y)=f(x,y)$ and
$g^{*}(x,y)=g(-x,-y)$. and for the case $f_{y}(0,0)<0$ and $g_{y}(0,0)>0$, we
can provide a reduction from CCI with functions $f^{*}(x,y)=f(-x,-y)$ and
$g^{*}(x,y)=g(-x,-y)$. Note that flipping the signs of the inputs of $f$ or
$g$ does not influence any second partial derivative, while it does negate the
first partial derivatives; therefore the mentioned starting points for the
reductions can all be seen to satisfy the conditions from Lemma 24.

As an example we discuss the case $f_{y}(0,0)>0$ and $g_{y}(0,0)>0$. We want
to give reduction from the problem CCI with functions $f^{*}(x,y)=f(-x,-y)$
and $g^{*}(x,y)=g(x,y)$; we denote this CCI variation by $\textrm{CCI}^{*}$.
So suppose that $(\delta,\Phi)$ is a $\textrm{CCI}^{*}$ instance. Now we will
construct a CCI instance $(\delta,\Psi)$ (with the $f$ and $g$ from the
theorem statement). We add every variable of $\Phi$ to $\Psi$, and for every
such variable $x$ we also add an extra variable
$\left\llbracket-x\right\rrbracket$, together with a constraint enforcing
$x+\left\llbracket-x\right\rrbracket=0$. Furthermore, we copy every constraint
from $\Phi$ to $\Psi$, except for constraints of the form $f^{*}(x,y)\geq 0$,
these are replaced by
$f(\left\llbracket-x\right\rrbracket,\left\llbracket-y\right\rrbracket)\geq
0$. This finishes the construction. ∎

As a final result in this section, we prove Theorem 8 as well. To do this, we
start from Corollary 20 and convert this to a result about CE-EXPL.

######  Lemma 25.

Let $U\subseteq\mathbb{R}$ be a neighborhood of $0$, and let $f\colon
U\to\mathbb{R}$ be a function which is 2 times differentiable such that
$f(0)=0$ and $f^{\prime}(0),f^{\prime\prime}(0)\in\mathbb{Q}$ with
$f^{\prime\prime}(0)\neq 0$. Now the problem CE-EXPL is
$\exists\mathbb{R}$-hard.

###### Proof.

We apply Corollary 20 to the case where $g=f$ to find that in this case CCI-
EXPL is $\exists\mathbb{R}$-hard. We can reduce this problem to CE-EXPL. Let
$(\delta,\Phi)$ be a CCI-EXPL instance. Now we construct an CE-EXPL formula
$\Psi$. We copy all constraints of the form $x+y=z$, $x\geq 0$ and $x=\delta$
from $\Phi$. For every constraint $y\geq f(x)$ we introduce two new variables
$\left\llbracket f(x)\right\rrbracket$ and $\left\llbracket
y-f(x)\right\rrbracket$, which we restrict by constraints

$\displaystyle\left\llbracket f(x)\right\rrbracket$ $\displaystyle=f(x),$
$\displaystyle y$ $\displaystyle=\left\llbracket
y-f(x)\right\rrbracket+\left\llbracket f(x)\right\rrbracket,\text{ and}$
$\displaystyle\left\llbracket y-f(x)\right\rrbracket$ $\displaystyle\geq 0.$

In a similar manner we replace every constraint $y\leq f(x)$ by introducing
new variables $\left\llbracket f(x)\right\rrbracket$ and $\left\llbracket
f(x)-y\right\rrbracket$ and imposing the constraints

$\displaystyle\left\llbracket f(x)\right\rrbracket$ $\displaystyle=f(x),$
$\displaystyle\left\llbracket f(x)\right\rrbracket$
$\displaystyle=\left\llbracket f(x)-y\right\rrbracket+y,\text{ and}$
$\displaystyle\left\llbracket f(x)-y\right\rrbracket$ $\displaystyle\geq 0.$

This completes the construction. It can easily be checked that every solution
of $\Phi$ corresponds to a solution of $\Psi$, and vice versa. ∎

See 8

###### Proof.

This proof is very similar to that of Lemma 24. Without loss of generality, we
may assume that $f_{y}(0,0)\neq 0$, otherwise we can swap the variables. Using
the implicit function theorem, we can write the condition $f(x,y)=0$ in some
neighborhood $(U^{\prime})^{2}\subseteq U^{2}$ of $(0,0)$ as
$y=f_{\textrm{expl}}(x)$, where $f_{\textrm{expl}}$ is some $C^{2}$-function
$U^{\prime}\to\mathbb{R}$. Using the fact that the curvature of $f$ is
nonzero, the implicit function theorem also tells us that
$f_{\textrm{expl}}^{\prime\prime}(0)\neq 0$.

Since $f(x,y)=0$ if and only if $y=f_{\textrm{expl}}(x)$, we find that the
problem CE is equivalent to the problem CE-EXPL, which we know to be
$\exists\mathbb{R}$-hard by the previous lemma. We conclude that also CE is
$\exists\mathbb{R}$-hard. ∎

##  3 Packing

In this section we will apply the result from the previous section to prove
$\exists\mathbb{R}$-completeness of packing convex polygons into a square
container under rotations and translations.

See 1

$\exists\mathbb{R}$-membership has been proven in Section 1 of [5]; this
follows fairly easily by applying a result from Erickson, Hoog and Miltzow
[24].

To prove $\exists\mathbb{R}$-hardness, we will use the framework by
Abrahamsen, Miltzow and Seiferth [5]. They used this framework to prove
hardness of a broad number of packing problems, however, the case of packing
convex polygons in a square container was left open. This is because of the
difficulties of encoding the constraint $x\cdot y\leq 1$ in this specific
setting. Using Theorem 10 on the classification of constraint satisfaction
problems, it is not necessary anymore to find a gadget encoding exactly
$x\cdot y\leq 1$. It becomes sufficient to find a gadget which encodes any
concave constraint on two variables, allowing a much greater freedom in
gadget-construction.

In Section 3.1, an overview of the framework from [5] is given. Some small
changes to this framework are necessary to allow a reduction from CCI for
suitable $f$ and $g$, instead of the problem ETR-INV which was used in [5].
These changes will be discussed in Section 3.2. The new gadget used in the
construction will be discussed in Section 3.3.

###  3.1 Overview of Previous Work

#### RANGE-ETR-INV.

The paper [5] gives a reduction from the $\exists\mathbb{R}$-complete problem
RANGE-ETR-INV to the various packing problems; the hardness of RANGE-ETR-INV
is proven in Section 5 in [5]. We repeat the definition of RANGE-ETR-INV here:

######  Definition 26 (Definition 1 from [5]).

An ETR-INV formula $\Phi=\Phi(x_{1},\ldots,x_{n})$ is a conjunction

$\left(\bigwedge_{i=1}^{n}1/2\leq x_{i}\leq
2\right)\wedge\left(\bigwedge_{i=1}^{m}C_{i}\right),$

where $m\geq 0$ and each $C_{i}$ is of one of the forms

$x+y=z,\quad x\cdot y=1$

for $x,y,z\in\\{x_{1},\ldots,x_{n}\\}$.

######  Definition 27 (Definition 2 from [5]).

An instance $\mathcal{I}=[\Phi,\delta,(I(x_{1}),\ldots,I(x_{n}))]$ of the
RANGE-ETR-INV problem consists of an ETR-INV formula $\Phi$, a number
$\delta:=2^{-l}$ for a positive integer $l$, and, for each variable
$x\in\\{x_{1},\ldots,x_{n}\\}$, an interval $I(x)\subseteq[1/2,2]$ such that
$|I(x)|\leq 2\delta$. For every inversion constraint $x\cdot y=1$, we have
either $I(x)=I(y)=[1-\delta,1+\delta]$ or $I(x)=[2/3-\delta,2/3+\delta]$ and
$I(y)=[3/2-\delta,3/2+\delta]$. We are promised that $V(\Phi)\subset
I(x_{1})\times\cdots\times I(x_{n})$. The goal is to decide whether
$V(\Phi)\neq\emptyset$.

#### WIRED-INV.

In Section 5.8 of [5] an auxiliary problem WIRED-INV is introduced. An
instance of this problem consists of a RANGE-ETR-INV instance together with a
wiring diagram. Such a diagram is a geometric representation of the ETR-INV
formula, where every variable $x$ is represented by two wires
$\overrightarrow{x}$ and $\overleftarrow{x}$, and every constraint is
represented by two constraint boxes intersecting some of these wires. See
Figure 8 for a drawing of such a wiring diagram.

Figure 8: A wiring diagram corresponding to the formula
$x_{2}+x_{3}=x_{1}\wedge x_{1}\cdot x_{2}=1$. This figure is taken with
permission from [5].

#### Main idea construction.

Next, this wiring diagram needs to be converted into a packing instance. For
this, we use an instance with $\delta=O(n^{-300})$. In the conversion, every
wire is converted to a lane of variable pieces, which can move horizontally,
but not vertically. The horizontal position of each of these pieces encodes
the value of the corresponding variable. Every constraint box of the wiring
diagram is replaced by a gadget. The idea behind the construction is described
in more detail at the start of Section 2 of [5]. After this part of the
construction, the container is a 4-monotone polygon. A 4-monotone polygon is a
polygon that consists of two $x$-monotone and two $y$-monotone polygonal
curves. See Figure 9 for a sketch of an instance which might result from this
construction.

Figure 9: A sketch of the instance of , broken over six lines, we get from the
wiring diagram in Figure 8 (except that the order of the inverters has been
swapped to decrease the number of crossings). The adders and inverters are
marked with gray boxes. This figure is taken from [5].

#### Fingerprinting.

For the construction as mentioned in the previous paragraph, it is important
that in every valid placement, all the pieces are placed almost as intended;
it should not be allowed to place the pieces in a completely different
configuration. To ensure this, a technique called fingerprinting is used,
which is described in Section 6 of [5]. To apply this technique, it is
important that every pieces has some corner where its angle is in
$[5\pi/180,\pi/3]$, such that this angle is sufficiently different from all
other angles of all other pieces. Furthermore, it is important to keep the
slack $\mu$ low. The slack is the area of the container minus the total area
of all the pieces. See Figure 10 for an illustration of this technique and its
underlying idea.

Figure 10: (a): A pocket and an augmentation that fit perfectly together as in
a jigsaw puzzle. If non-convex pieces are allowed, this mechanism can be
easily used to enforce a canonical placement of all the pieces. The idea for
convex polygonal pieces is similar, but technically more intricate. (b): A
wedge of the empty space and a piece which fit together. (c): The corner of
the piece we are fingerprinting is marked with a dot. (d) and (e): Two
examples where space is wasted because a wedge is not occupied by a piece with
a matching angle. This figure is taken from [5].

#### Correctness of the reduction.

The proof of correctness of the reduction happens in a number of steps, which
are described in Section 2 of [5]. Most of these steps happen separately for
every gadget in Sections 7 and 8. Here we will give a brief overview of the
steps.

The first step is to show that every solution to the original RANGED-ETR-INV
instance gives rise to a solution of the packing instance. The remaining steps
are concerned with proving that any solution to the packing instance also
gives a solution to the RANGED-ETR-INV instance.

First, for every gadget, a set of canonical placements are defined. These are
the “intended” placements, where all pieces are in the right positions and
have the intended edge-edge contacts. Furthermore, a valid placement is any
placement that respects the condition that no pieces should overlap and all
the pieces are inside the container. The next step is to prove using
fingerprinting that any valid placement of all the pieces is almost-canonical.
This means that each piece is moved by a distance of at most $n^{-1}$ from a
canonical placement. Now it is proven that any almost-canonical placement is
also an aligned $N\mu$-placement. In such a placement, every variable piece
should be correctly aligned, and should furthermore encode a variable in the
range $[m-N\mu,m+N\mu]$, where $N=O(n^{4})$ is the total number of gadgets in
the packing instance. The variable $\mu=O(n^{-296})$ is the total amount of
slack in the instance, and $m$ is the midpoint of the interval $I(x)$
corresponding to the variable piece.

After this, it needs to be shown that all the variable pieces corresponding to
a single variable actually encode the same value. For this purpose, a
dependency graph $G_{x}$ is introduced for every variable $x$. The vertices of
this graph are all the variable pieces which encode this variable. Two of
those vertices are connected by a directed edge if one of the corresponding
pieces enters some gadget, and the other leaves the same gadget. It needs to
be proven that for any such edge $(p_{1},p_{2})$ of $G_{x}$, we have $\langle
p_{1}\rangle\leq\langle p_{2}\rangle$ where $\langle p\rangle$ indicates the
value encoded by piece $p$. The packing instance was constructed in such a way
to ensure that this graph $G_{x}$ contains a large cycle $K_{x}$. This implies
that every piece in this cycle encodes exactly the same value $\langle
K_{x}\rangle$. See Figure 11 for a visualization of the graph $G_{x}$.

Figure 11: An abstract drawing of the dependency graphs of the instance we get
from the wiring diagram in Figure 8 and how the graphs connect to the gadgets
for addition and inversion constraints. The number of vertices on the cycles
and paths are neither important nor correct. This figure is taken from [5].

The last step of the correctness proof consists of showing that for any
addition constraint $x+y=z$ of $\Phi$, we actually have $\langle
K_{x}\rangle+\langle K_{y}\rangle=\langle z\rangle$, and similarly that for
every inversion constraint $x\cdot y=1$ we have $\langle
K_{x}\rangle\cdot\langle K_{y}\rangle=1$. From this it follows that any valid
packing indeed encodes a solution to $\Phi$.

#### Square container.

Finally in Section 9 of [5], it is described how the packing instance with a
4-monotone container can be converted to a packing instance with a square
container.

###  3.2 Changes to the framework

#### CCI and WIRED-CCI.

As mentioned in the previous section, the proof from [5] works by reducing
from RANGED-ETR-INV via the problem WIRED-INV. In the reduction in this paper,
we will instead reduce from CCI via a new problem WIRED-CCI. The specific
version of CCI which is used, uses the following polynomials $f$ and $g$:

$\displaystyle f(x,y)$ $\displaystyle=(x-1)(y-1)-1,\textrm{ and}$
$\displaystyle g(x,y)$
$\displaystyle=(x-1)^{2}+\left(\frac{1}{4}y-1\right)^{2}-2.$

Note that those are just linear transformations of the polynomials $xy-1$ and
$x^{2}+y^{2}-1$. After expanding the brackets in this definition, it is
straightforward to check that these do indeed satisfy the necessary properties
applying Theorem 10. For the rest of this section on packing, any reference to
CCI or the polynomials $f$ and $g$ will refer to this specific definition.

An instance of WIRED-CCI consists of a CCI instance together with a wiring
diagram. Let $\Phi$ be a CCI formula, now we define a wiring diagram of this
formula $\Phi$ in almost the same way as is done in Section 5.8 from [5], see
also Figure 8. The only difference in the definition concerns the constraint
boxes which are needed in the diagram. Addition constraints are still modeled
in the same way: for a constraint $x_{i}+x_{j}=x_{k}$, we have two constraint
boxes for enforcing respectively $x_{i}+x_{j}\leq x_{k}$ and $x_{i}+x_{j}\geq
x_{k}$. The first box should intersect the right-oriented wires
$\overrightarrow{x_{i}}$, $\overrightarrow{x_{j}}$ and
$\overrightarrow{x_{k}}$ in positions $\ell_{1}$, $\ell_{2}$ and $\ell_{3}$
respectively. The second box should intersect the left-oriented wires
$\overleftarrow{x_{i}}$, $\overleftarrow{x_{j}}$ and $\overleftarrow{x_{k}}$
in positions $\ell_{1}$, $\ell_{2}$ and $\ell_{3}$ respectively.

For each constraint of the form $f(x_{i},x_{j})\geq 0$, we have a single
constraint box which intersects the left-oriented wires
$\overleftarrow{x_{i}}$ and $\overleftarrow{x_{j}}$ in positions $\ell_{1}$
and $\ell_{2}$. Similarly for each constraint of the form $g(x_{i},x_{j})\geq
0$ we should have a single constraint box intersecting the right-oriented
wires $\overrightarrow{x_{i}}$ and $\overrightarrow{x_{j}}$ in positions
$\ell_{1}$ and $\ell_{2}$.

Lastly, constraints of the form $x_{i}\geq 0$ or $x_{1}=\delta$ do not need to
be encoded in the wiring diagram in any way. The reason for this is that we
will directly encode these constraints in the anchor-gadgets, so no separate
constraint boxes are needed.

######  Definition 28 (WIRED-CCI, modified from [5, Definition 42]).

An instance $\mathcal{I}=[\mathcal{I}^{\prime},D]$ of the _WIRED-CCI problem_
consists of an instance $\mathcal{I}^{\prime}$ of CCI together with a wiring
diagram $D$ of the CCI formula $\Phi(\mathcal{I}^{\prime})$.

######  Lemma 29 (Modified from [5, Lemma 43]).

Given an CCI formula $\Phi$ with variables $x_{1},\ldots,x_{n}$, we can in
$O(n^{4})$ time construct a wiring diagram of $\Phi$. Therefore, the problem
WIRED-CCI is $\exists\mathbb{R}$-hard, even when $\delta=O(n^{-c})$ for any
constant $c>0$.

###### Proof.

The proof is completely analogous to that of Lemma 43 of [5]. The idea is that
we can construct the wiring diagram from left to right. For every constraint
we first swap some pairs of wires to make sure that the correct wires are on
top, and then we insert a constraint box into the diagram. This reduction
requires $O(n^{4})$ time, where $n$ is the number of variables in $\Phi$,
since there are at most $O(n^{3})$ distinct constraints, and for each of those
constraints at most $O(n)$ swaps need to be inserted. ∎

Using Lemma 29, it follows that the problem WIRED-CCI is
$\exists\mathbb{R}$-hard. Using the framework from Abrahamsen, Miltzow and
Seiferth [5] with the modifications below, we get a reduction from WIRED-CCI
to the desired packing problem. In this reduction the teeter-totter is used
for encoding constraints of the form $f(x,y)\geq 0$ and the wobbly gramophone
is used for encoding constraints of the form $g(x,y)\geq 0$.

#### Variable pieces.

In the framework from [5], every variable $x$ of an ETR-INV formula comes with
an interval $I(x)\subset[1/2,2]$. Following this example, we also define
$I(x)$ for any variable of a CCI formula $\Phi$. We take:

$I(x)=\begin{cases}\\{\delta\\}&\text{if $\Phi$ has a constraint }x=\delta,\\\
[0,\delta]&\text{else, if $\Phi$ has a constraint }x\geq 0,\\\
[-\delta,\delta]&\text{otherwise.}\end{cases}$

Note that the construction from [5] only uses the fact that
$I(x)\subset[1/2,2]$ when translating between positions of pieces and the
corresponding variable values. This can still be done in our construction,
where we know that all intervals $I(x)$ are instead contained in
$[-\delta,\delta]$. For the reduction to work, it is merely necessary that
every interval $I(x)$ has size at most $2\delta$, which is still the case.

#### Gadgets.

We can directly reuse most of the gadgets from [5]. In particular we keep
using the anchor, swap, split, adder and teeter-totter. The seesaw and
gramophone are not used anymore, those are replaced by the new wobbly
gramophone, which will be introduced in more detail later. The anchor is
placed at both ends of every variable lane, and ensures that the left-oriented
and right-oriented lanes corresponding to the same variable also encode the
same value. The swap is used when two lanes need to cross. The split
duplicates one of the lanes; this is necessary for embedding the adders and
teeter-totters in the construction. The adder can be used for encoding both
constraints of the form $x+y\leq z$ and $x+y\geq z$. Finally, the teeter-
totter encodes constraints of the form $xy\geq 1$, and the wobbly gramophone
will encode constraints of the form $g(x,y)\geq 0$. An overview of the gadgets
is given in Figure 12.

Figure 12: (a): anchor, (b): swap, (c): adder, (d): teeter-totter, (e): wobbly
gramophone

The anchor, swap, split and adder gadgets can be directly used without any
modification. It should be noted that the anchor always ensures that for any
valid packing, the value of some variable $x$ encoded by this packing is
always in the interval $I(x)$. Therefore, because of our definition of the
intervals $I(x)$, the anchor automatically enforces the constraints of the
form $x=\delta$ and $x\geq 0$.

Some more care is needed for using the teeter-totter. The original teeter-
totter is used to encode $xy\geq 1$ in some neighborhood of either $(1,1)$ or
$(2/3,3/2)$. For our result, we however need a constraint in a neighborhood of
$(0,0)$. To obtain this, we use the teeter-totter for encoding $xy\geq 1$
around $(1,1)$, but consider both the variables to be translated by $-1$. In
this way we can use exactly the same gadget to enforce $(x+1)(y+1)\geq 1$ in a
neighborhood of $(0,0)$. This new constraint is equivalent to $f(x,y)\geq 0$
with the $f$ defined earlier.

Figure 13: (a) The original gramophone from [5]. (b) The concept behind the
new gadget. Just like in the original gramophone, the gray pieces marked $k$
cannot move and can be thought of representing a constant. Now the green piece
prevents the tip $c$ of the pink piece from coming too close to the point $p$
on the container boundary, thereby enforcing a constraint of the form
$x^{2}+y^{2}\geq 1$.

###  3.3 Gadget

The next step in proving $\exists\mathbb{R}$-hardness of the packing problem
of convex polygons is to find a suitable gadget which encodes some concave
constraint on two variables, while using only convex pieces. Here we introduce
this new gadget, the wobbly gramophone, which is a modification of the
gramophone gadget from [5]. The idea behind the gadget is to change the
original gramophone by replacing the curved boundary by a rotating piece. See
Figure 13. The exact concave constraint enforced by the actual form of this
gadget will be $(x-1)^{2}+\left(\frac{1}{4}y-1\right)^{2}\geq 2$.

For the rest of this section, we will write $\Phi$ for the CCI formula which
we are reducing to a packing instance, and we let $\mathbf{p}_{i}$ be the set
of all pieces which are part of the first $i$ gadgets of the constructed
packing instance.

We will start by explaining the principle behind the simplified version of the
gadget. Then the actual wobbly gramophone will be described, and it will be
shown that it satisfies all the properties which are necessary for embedding
it in the framework from [5].

#### Principle.

Just like in the original gramophone from [5], the new wobbly gramophone
contains a pink piece with a tip $c$, which encodes both the variables $x$ and
$y$. Instead of having a fixed curve which bounds the corner $c$, we use a
rotating rectangular piece of width $1$ (the green piece) which enforces that
the distance between $c$ and some corner $p$ on the outside boundary is at
least $1$. Therefore this exactly encodes a constraint of the form
$x^{2}+y^{2}\geq 1$ in a neighborhood of the point $(0,-1)$. In the actual
gadget, we will use a scaled and translated version of this constraint, as
will be described next.

Figure 14: The actual wobbly gramophone. Color codes: 1 yellow, 2 gray, 3
blue, 4 turquoise, 5 orange, 6 green, 7 pink, 8, 9 red, 10, 11, 12, 13, 14
yellow, 15, 16 red, 17, 18, 19, 20, 21 blue, 22, 23 red, 24, 25, 26 gray.
Figure 15: The fingerprinting subgadget. Color codes: 1 red, 2 orange, 3 blue,
4 pink, 5 turquoise. Figure 16: The installation manual of the wobbly
gramophone, taken from [5].

#### Actual gadget.

A more accurate drawing of the actual wobbly gramophone can be seen in Figure
14. Here all the side-lengths of the pieces should be chosen in such a way to
make sure the total amount of empty space (slack) is only $O(\delta)$. This
gadget differs on quite some aspects from the simplified drawing in Figure 13.
First we observe that the only pieces which are involved in enforcing the
correct constraint, are pieces with numbers 1, 2, 3, 5, 6, 7, 10, 21 and 24;
the rest of the pieces are necessary just for fingerprinting purposes.

The pieces numbered 1 and 10 should have edge-edge contacts with the pink
piece. Together these pieces enforce that the pink piece has the intended
orientation, and they fix the $x$-coordinate of the pink piece. The pieces 2,
3, 4, 5, 21 and 24 together form a swap gadget, as described in [5].
Furthermore, the gray pieces all have a fixed position, so they encode some
constant $k$. However, instead of freely choosing the corners of pieces 2, 3,
21 and 24 for fingerprinting (as is done for the original gramophone), we
always take these angles to be $\arctan(1/2)$. In this way the slope of the
slanted sides of these pieces is exactly $1/2$. Now if the value encoded by
pieces 3 and 21 is increased by $\Delta y$, then the orange piece 5 will move
up by $\frac{1}{4}\Delta y$. Stated differently, if piece 3 and 21 encode some
variable $y$, then the $y$-coordinate of the orange piece encodes
$\frac{1}{4}y$, and the $y$-coordinate of the pink piece encodes some variable
$y^{\prime}$ which satisfies $y^{\prime}\geq\frac{1}{4}y$.

The green piece (6) should have distance exactly $\sqrt{2}$ between its long
sides. (Note that this can be done while still ensuring all corners of this
piece have rational coordinates. To see this, note that the two parallel lines
$y=-x$ and $y=-x+2$ have exactly distance $\sqrt{2}$.) In this way, the green
piece enforces that the distance between corner $c$ of the pink piece and
corner $p$ of the outside boundary is at least $\sqrt{2}$. Since the $x$\- and
$y$-coordinates of the pink piece encode the variables $x$ and $y$ in some
sense, we find that the gadget enforces the constraint
$(x-1)^{2}+\left(\frac{1}{4}y-1\right)^{2}\geq 2$ around the point
$(x,y)=(0,0)$. Note that that $(x,y)=(0,0)$ corresponds exactly to the case
where the $x$\- and $y$-coordinates of corner $p$ are both 1 larger than the
$x$\- and $y$-coordinates of corner $c$.

The rest of the pieces, which form the right half of the gadget, have as a
purpose to fingerprint the pieces 10, 21 and 24. This is necessary since these
three pieces are not fingerprinted at their corners next to the orange and
pink pieces, as is done in the gramophone described in [5]. The right half
consists of three subgadgets, as drawn in Figure 15. Such a subgadget allows
us to fingerprint a variable piece from the right instead of from the left.

It is important that the fingerprinting corner of piece 13 (in Figure 14) is
strictly smaller than that of piece 14; this ensures that piece 13 attains its
maximum width at the top, and therefore cannot be translated or rotated
without pushing piece 14 to the right. Similarly, the fingerprinting corner of
piece 20 should be smaller than the fingerprinting corner of piece 21.

Embedding this gadget into the total construction is done in exactly the same
way as the embedding of the gramophone from [5]. See Figure 16. In particular
there is a separate lane introduced for the constant $k$, which ends
immediately before and after the gadget. This lane is ended in such a way to
ensure that the first variable piece of this lane encodes at least $0$, and
the last piece encodes at most $0$.

#### Canonical placements and solution preservation.

The variable pieces in the wobbly gramophone are pieces 1, 3, 10, 12, 14, 17,
19 and 21. Furthermore we will also treat pieces 2, 24 and 26 as variable
pieces, even though they do not encode actual variables, but they do encode a
constant $k$.

We take the canonical placements to be those where the boundary and the