Closed Sets and Operators thereon:

Representations, Computability and Complexity
Carsten Rösnick-Neugebauer
Supported by the German Research Foundation (DFG) with project
and by the Marie Curie International Research
Staff Exchange Scheme Fellowship  within the 7th European
Community Framework Program.
A preliminary version (extended abstract) have been appeared in Proc. CCA'2013.
Some parts have also been published in the author's PhD thesis <cit.>.

Carsten Rösnick-Neugebauer

Technische Universität Darmstadt, Germanyuntil March 2015

The TTE approach to Computable Analysis is the study of so-called
representations (encodings for continuous objects such as reals, functions,
and sets) with respect to the notions of computability they induce.
A rich variety of such representations had been devised over the past
decades, particularly regarding closed subsets of Euclidean space plus
subclasses thereof (like compact subsets). In addition, they had been
compared and classified with respect to both non-uniform computability of
single sets and uniform computability of operators on sets.
In this paper we refine these investigations from the point of view of
computational complexity.

Benefiting from the concept of second-order representations and complexity
recently devised by Kawamura & Cook (2012), we determine parameterized
complexity bounds for operators such as union, intersection, projection,
and more generally function image and inversion. By indicating natural
parameters in addition to the output precision, we get a uniform view on
results by Ko (1991-2013), Braverman (2004/05) and Zhao & Müller (2008),
relating these problems to the $\PTime$/$\UPTime$/$\NPTime$ question in
discrete complexity theory.

§ INTRODUCTION

Closed subsets of Euclidean space, and in particular subclasses thereof like
compact subsets, are important throughout many parts of pure theoretical
mathematics, but also of no less relevance in disciplines like numerical
analysis, convex optimization, or computational geometry. It is
necessary to first define encodings for sets in order to describe computations
on them which can be performed in a reasonably realistic computational model
(which can even be implemented and used in practice <cit.>).
We choose the function oracle Turing machine model as in
<cit.> with encodings (functions of form
$\phi \colon \Sast \to \Sast$) of continuous objects (reals, functions, sets)
are passed to as oracles. The accompanying
complexity notion is the one of second-order polynomials <cit.>
– with the explicit addition of parameters which leads to a second-order
equivalent of discrete parameterized complexity <cit.>.

The introduction of such encodings for sets, called representations in
the TTE-branch of Computable Analysis,
constitutes the first of two parts of this paper.
One possible representation, $\distrep$, of a closed non-empty set
$S \subseteq \IR^d$ is by a function $\phi$ approximating its distance
function $d_S$ at any point up to arbitrary precision.
Another representation, $\setrep$, is as follows:
Given a point $q$ and a precision parameter $n$, assert either
$q$ is of distance less than $2^{-n}$ to $S$, or that it is of distance
greater than $2 \cdot 2^{-n}$. Both representations allow for printing an
arbitrarily precise picture of the respective set. So are these two
representations computably equivalent, and if, how do they relate
complexity-wise? While computably equivalent in any dimension $d$, they are
only polynomial-time equivalent in dimension $d = 1$. From dimension $d = 2$
onward their non-uniform polynomial-time relation (, $S$ is
polynomial-time computable with respect to representation $\distrep$ if it is
for $\setrep$) has been linked to the $\PTime$ vs. $\NPTime$
question <cit.>. Several more representations had been suggested
and compared with respect to their computable equivalence
The complexities of these relations, and in particular the uniform
formulations (, the complexity of an operator translating between two
representations) of them, appear to be mostly unmentioned or unknown (except
for a few examples <cit.>). We strengthen these
previously known equivalence results from mere computable equivalence to
parameterized polynomial-time equivalence, and prove uniform
exponential lower bounds for the other relations.
For dimension $d = 2$ these uniform (non-)polynomial-time equivalence results
relate to complexity results for subsets of $\IR^2$ with respect to various
representations <cit.>; and they allow us to restate
complexity results like for Julia sets <cit.>
with respect to polynomial-time equivalent representations.

The second part of this work is constituted by an excursion about operations
on above sets; like intersecting or joining pairs of sets, the projection to
lower dimensional subspaces or generating the convex hull, but also forming
the image or local inverse of a function with respect to a given set.
The situation concerning their parameterized complexity is similar to
that for representations of sets: Operators on closed, compact or regular
subsets have been considered with respect to computability (,
and non-uniform complexity bounds (,
<cit.>, <cit.>),
but it appears that less is known about the uniform complexity of operators
(exceptions include
In addition, complexity bounds of  projection
and function inversion had been linked to classical problems from discrete
complexity theory, namely $\PTime$ vs. $\NPTime$ and $\PTime$ vs. $\UPTime$.
Results like these are in the spirit of well-known ones for maximization and
integration of functions <cit.> (we refer the reader to
<cit.> for an overview and more examples of
this kind).

In this paper we present uniform worst-case parameterized complexity bounds
for all of the aforementioned operators. Providing operators through
parameters with more information about their arguments turns out to be
valuable and fruitful approach to achieve uniformity and also allows for a
fine-grained perspective on their inherent complexity.[
Take the projection of a subset of $\IR^d$ to its first component as an
The question whether a given point $q$ is contained in the projection is
uncomputable as long as no information about a bound of the set is given.]
In addition to upper bounds we also present exponential-time lower bounds,
thus extending upon the former non-uniform bounds that depended on
believed-to-be-hard problems from discrete complexity theory.

§.§ Results obtained in this paper

Primarily based on <cit.>, <cit.>,
<cit.> and <cit.>, we introduce five representations
in <ref>: $\distrep$ and $\reldistrep$, $\setrep$,
$\gridrep$, and $\wmemrep$. Each representation will depend on a fixed yet
arbitrary norm a dependence we will show in
<ref> to be of “polynomial-time irrelevance”
for all but one representation ($\distrep$:
<ref>). We furthermore compare
relations between representations by means of (parameterized) polynomial-time
translations; and observe that, although they are all (uniformly)
computably equivalent over convex regular sets
<cit.>, the same is only true for (parameterized)
polynomial-time reductions for subsets of $\IR^{d = 1}$
(<ref>), but partially fails from dimension
$d = 2$ onward. There even emerges, in a sense, a hierarchy:
$\wmemrep$ forms the poorest, $\distrep$ the richest
representation, and $\reldistrep$, $\setrep$, $\gridrep$ are parameterized
polynomial-time equivalent over compact sets
Parameterized polynomial-time equivalence of $\wmemrep$ with $\distrep$
(hence of all of the former representations) is finally achieved if
restricted to compact convex regular sets <ref>.

<ref> then uses the formerly unveiled connections between
representations by discussing the complexity of operators. Operators include
$\dsoch$ (finding some point in a set; the presumably most basic set
operation) and $\dsocup$, which are fully polynomial-time computable
for all of the above representations but $\wmemrep$); and $\dsocap$, which
(in contrast to the former result) is easy only for $\wmemrep$. More
involved operators, $\dsoinv$ and $\dsoimg$, are discussed in
<ref>: We prove that $\dsoinv$ is parameterized
polynomial-time computable for Lipschitz-continuous functions whose inverse
is also Lipschitz continuous (<ref>) which
fits right in the gap between naive exponential-time algorithms and results
of Ko <cit.>, the latter relating non-uniform
$\dsoinv$ for a more general class of functions to the (considered to be hard)
question whether $\PTime \neq \UPTime$ holds true.

§.§ Preliminaries, nomenclature

We introduce some notations and concepts we frequently use throughout this
Let $\Sigma$ be the binary alphabet $\{0,1\}$, $\Sast$ denotes the set of
finite $0/1$-strings, $\Cantor$ the set of $0/1$ sequences
(isomorphic to $\Sigma^{(\Sast)}$, the set of all total functions from
$\Sast$ to $\Sigma$), and $\Baire \dfeq (\Sast)^{(\Sast)}$ the set of all
total functions from $\Sast$ to $\Sast$.
A finite string $s = s_1 \cdots s_k \in \Sast$ with $s_i \in \Sigma$ is also
called word.
The length of $s$ (as above) is defined by $\len{s} \dfeq k$, and
$\eword$ denotes the unique word of length $0$ (the empty word).

We further consider the sets $\Cantor$ and $\Baire$ as topological spaces
equipped with the product topology (equip $\Sigma$, $\Sast$ with the
discrete topology).

Let $\IN \dfeq \{0\} \cup \IN_+$ with $\IN_+ \dfeq \{1,2,3,\dots\}$,
and abbreviate the binary logarithm of $x$ by $\lb x \dfeq \log_2 x$.
By $\ID_m \dfeq \st{a/2^m}{a \in \IZ}$ we denote the set of dyadic
rationals of precision $m \in \IZ$, and set
$\ID \dfeq \bigcup_{m \in \IZ} \ID_m$.
Let further $\bnatrep \dffn \IN \to \Sast$ denote the usual binary
coding of naturals as words, $\unatrep$ denotes the unary coding
which we usually abbreviate by $0^n \dfeq \unatrep(n)$.
Even though $\unatrep$ is not surjective and thus does not admit an inverse,
we like to understand by $\unatrep^{-1}$ the mapping
$s \in \Sast \mapsto \len{s} \in \IN$.
Note that the notions of binary and unary encodings naturally extend to the
set of integers by embedding $\IZ$ into $\IN$.
By abuse of notations, we casually write $0^{k}$ for the unary coding of
an integer $k$.
Pairing functions (usually total, bijective, computable and invertible in
polynomial time, although we do not need them to be surjective) are denoted
by $\encdot_X \colon X \times X \to X$ whereby the “${}_X$” will be usually
clear from context (typically $\IN$, $\Sast$ or $\Baire$) and henceforth

Explicitly, $\enc{s,t}_{\Sast} \dfeq
\bnatrep \big( \enc[1]{\bnatrep^{-1}(s), \bnatrep^{-1}(t)}_{\IN} \big)$
with $\encdot_{\IN}$ being the Cantor pairing function.
Further define the pairing function $\enc{\phi,\psi}$ on Baire space
$\Baire$ through
$\enc{\phi,\psi}(\eword) \dfeq \eword$,
$\enc{\phi,\psi}(0\,s) \dfeq 0^{\len{\psi(s)}}\,1\,\phi(s)$, and
$\enc{\phi,\psi}(1\,s) \dfeq 0^{\len{\phi(s)}}\,1\,\psi(s)$
for all $s \in \Sast$.
The binary encoding $\dyrep[d] \dffn \ID^d \to \Sast$ of dyadic rationals
is recursively defined:
Let $\dyrep[1] \dffn a/2^{n} \mapsto \enc[1]{\bintrep(a),0^n}_{\Sast}$
and for $d \geq 2$ let $\dyrep[d] \dffn (q_1,\dots,q_d)
\mapsto \enc[1]{ \dyrep[1](q_1), \dyrep[d-1](q_2,\dots,q_d) }_{\Sast}$.

A normed (vector) space is a pair $(X,\normdot)$ of a vector space $X$
together with a norm $\normdot$ on $X$.

A set $S \subseteq X$ is open in $X$ if it is the set of its
inner points, , $\inner{S} = S$, and closed (in $X$) if it is the closure
of itself, , $\cls{S} = S$. The boundary is defined as
$\boundary{S} \dfeq S \setminus \inner{S}$.

On $(\IR^d, \normdot)$ we denote closed balls with center $x \in \IR^d$
and radius $\delta > 0$ by $\clb[\normdot]{x}{\delta} \dfeq
\st[0]{y \in \IR^d}{\norm{x-y} \leq \delta}$ or simply by
$\clb{x}{\delta}$ if the norm used is understood.
Similarly denote open balls as $\opb[\normdot]{x}{\delta}$.
Whenever useful, we use the abbreviation
$\ID^d_n(R) \dfeq \ID^d_n \cap \cball(0,R)$.
A “ball” (actually a neighborhood) around a set $S \subseteq \IR^d$ of
radius $\delta > 0$ is defined through the union of balls around the points
of $S$, , $\cball(S,\delta) \dfeq \bigcup_{x \in S} \cball(x,\delta)$,
and similarly for open balls.
The same works in the reverse direction, , for negative radii:
Denote by $\cball(S,-\delta) \dfeq
\st{x \in \IR^{d}}{\cball(x,\delta) \subseteq S}$
the (possibly empty) set of all points $x$ lying $\delta$-deep in $S$.
Further define hollow closed balls centered at $x$ with inner radius
$\delta' > 0$ and outer radius $\delta \geq \delta'$ through
$\cball_{\normdot}(x,\delta,\delta') \dfeq
\clb[\normdot]{x}{\delta} \setminus \opb[\normdot]{x}{\delta'}$.

The domain and co-domain (also: image) of a function $f$ mapping from a set
$X$ into $Y$ are denoted by $\dom(f)$ and $\cod(f)$, respectively. Besides
total functions, $f \colon X \to Y$ with $\dom(f) = X$, we also consider
partial functions $f \parcol X \to Y$ ($f$ is defined only on a subset of $X$,
thus the “$\usubseteq X$”), and partial multi-valued functions as
$f \dffn X \mto Y$, $f(x) \subseteq Y$.
Phrased differently, a multi-valued partial function $f \dffn X \mto Y$ is
a partial function from $X$ into the powerset of $Y$.
The multi-valued assignment of an element $x \in X$ to a subset
$Y' \subseteq Y$ is abbreviated by $x \mmapsto Y'$.

§ MODEL, REPRESENTATIONS AND COMPLEXITY

All the concepts we discuss in this section are guided by the question how
computations on subsets of real vector spaces could be carried out on a
reasonably realistic machine model. Using a Turing-like machine model
(<ref>), we define encodings of sets through representations
(<ref>) and proceed by giving definitions for
computability and parameterized complexity

§.§ Computational models

Two mainstream models in Computable Analysis are the Type-2 Theory
of Effectivity <cit.> and the oracle Turing machine model
<cit.>. The former even yields a topological interpretation of
Therefore, we start
by introducing computability using the former model.
Carrying these notation over to the latter model will then allow us

to give suitable notion of complexity.
From a computational point, however, both models are equivalent.
The notions discussed in this section are based on
<cit.> and <cit.>.

§.§.§ Type-2 machines: computations on finite and infinite strings.

Type-2 machines extend upon classical Turing machines by operating on
infinite strings instead of finite ones, , on $\Cantor$
instead of $\Sast$. Such a machine consists of finitely many left-to-right
readable input and bidirectional working tapes, and one left-to-right writable
output tape.
A computation on finite strings is carried out as on classical Turing
machines: Given a type-2 machine $M$ with $k \in \IN$ input tapes
plus an input $(s_1,\dots,s_k) \in \Sast \times \dots \times \Sast$ to it,
$M$ either reads one symbol from one of its $k$ input tapes, reads or
writes one symbol on one of its working tapes, or writes a symbol on its output
tape. The same applies if the input is not a tuple of finite strings, but of
infinite ones from $\Cantor \times \dots \times \Cantor$.
Given such a machine $M$, we say it computes a partial function
$f \parcol \Sast \times \dots \times \Sast$ if it terminates on all inputs
$(s_1,\dots,s_k)$ from $f$'s domain and writes $f(s_1,\dots,s_k)$
symbol-by-symbol on the output tape.
As for the infinite case, $M$ computes a partial function
$f \parcol \Cantor \times \dots \times \Cantor \to \Cantor$ if $M$ continues
forever on input $(s_1,\dots,s_k)$ whilst producing $s \dfeq f(s_1,\dots,s_k)$
on its output tape.

Machines which have to run infinitely long to produce their answer would
certainly not deserve to be called “practicable”. The key here, however, is
that for every finite prefix of the input read a type-2 machine
produces a non-revisable finite prefix of the still infinitely long
correct output. We postpone discussing of the strong topological implications
to computability until <ref> and <ref>.

As for classical Turing machines, type-2 machines are also capable to compute
functions $f \parcol X_1 \times \dots \times X_k \to X'$ for sets $X_i, X'$
different from $\Cantor$ by encoding their elements through items from
$\Cantor$ (appropriate cardinalities assumed).
Following <cit.>, we call such encodings
representations. Building upon them, we formulate the computability of
functions $f \parcol X \to X'$ through realizers.

Let $X$ and $X'$ be sets.

* A representation of $X$ is a surjective partial function
$\reptpl \parcol \Cantor \to X$.

* An element $\phi \in \reptpl^{-1}[\{x\}]$ is said to be a
$\reptpl$-name of $x$.

Further assume $\reptpl$ and $\reptpl'$ to be representations of $X$ and
$X'$, respectively, and let $f \parcol X \to X'$ be some function.

* A function $g \parcol \Cantor \to \Cantor$ is called a
$(\reptpl,\reptpl')$-realizer of function $f$ if for all
$\phi \in \reptpl^{-1}\big[ \dom(f) \big]$,
$(\reptpl' \circ g)(\phi) = (f \circ \reptpl)(\phi)$ holds true.
A more visual way to think of realizers is by a commuting diagram:

\begin{equation*}
\xymatrix<EMAIL_ADDRESS>\Cantor \ar[r]^g \ar[d]^{ \reptpl } &
\Cantor \ar[d]^{ \reptpl' } \\
X \ar[r]^f &
\end{equation*}

* Function $f$ is called $(\reptpl,\reptpl')$-computable
(-continuous) if it has a computable (continuous)

The above notions
are reasonable in the
sense that topological continuity of a function corresponds to
$(\reptpl,\reptpl')$-continuity if $\reptpl$ and $\reptpl'$ are both
admissible (cf. <cit.>, <cit.>).

Note that all representations mentioned in this paper are admissible.

We present a few examples of representations in form of a definition.

* Representations $\unaryrep$ and $\binaryrep$ extend upon the
unary and binary encodings, $\unatrep^{-1}$ and $\binatrep^{-1}$
from $\Sast$ to $\Cantor$.[
To justify notational between $\bnatrep^{-1}$ and $\binaryrep$:
Computations are performed on the level of names (, objects
from $\Cantor$).

Objects like natural numbers or dyadic rationals, on the contrary,
are usually used “as the are”, , not encoded as words or
They are encoded back into words (via $\bnatrep$ or
$\unatrep$) not before the end of the respective argument.]
We say, a natural number $k \in \IN$ is represented by a
$\phi = 0\,b_0\,0\,b_1 \dots 0\,b_\ell\,1^\omega \in \Cantor$,
$\binaryrep \parcol \Cantor \to \IN$, if $\phi$ essentially is $k$'s
binary encoding: $\binaryrep(\phi) = \sum_{i=0}^\ell b_i 2^{i} = k$.
Its unary counterpart, denoted $\unaryrep$, can be obtained through
representing a natural number $k \in \IN$ by
$\phi \dfeq (0\,1)^k\,1^\omega \in \Cantor$.

We define a $\realrep$-name $\phi$ of a real number $x \in \IR$ to
be a suitably encoded sequence $(q_n)_n$ of dyadic rationals
$q_n \in \ID_n = \st{a/2^n}{a \in \IZ}$ (,
$\phi = \left< (q_n)_{n\in\IN} \right> \in \Cantor$;
cf. <cit.>) converging to $x$ in the sense
that $|q_n - x| \leq 2^{-n}$ holds true for all $n \in \IN$.

* Based on $\realrep$, a representation
$[\realrep \!\to\! \realrep] \parcol \Cantor \to \cfn(\IR)$ of
continuous functions $f \colon \IR \to \IR$ may intuitively be
understood as follows: A $[\realrep\shortto\realrep]$-name encodes
how ($\realrep$-names of) $x \in \IR$ are translated into
$\realrep$-names of $f(x)$ (cf. <cit.>
and <cit.>).

An important property of the TTE model and its
representations is due to its concise topological roots, resulting in the
Main Theorem in the TTE-branch of Computable Analysis.

Computability implies (topological) continuity.

Recall that $(\reptpl,\reptpl')$-computability by a Type-2 machine $M$ means
that $M$ maps finite prefixes of a $\reptpl$-name $\phi$ to finite prefixes of
a $\reptpl'$-name $\phi'$.

The reader is referred to <cit.> for detailed
explanations and proofs.

§.§.§ Oracle machines.

The type-2 model, and in particular the way we have introduced representations
so far, does not yield a viable notion of complexity:
Say $\phi$ is a $\realrep$-name of a real number $x \in \IR$ as
defined in <ref>(def:realrep), , an encoded sequence
$(q_n)_{n \in \IN}$ of dyadic rationals.
In order to access a specific element encoded through $\phi$,
say $q_N$, a type-2 machine has first to skip over a possibly large (compared
to the coding length of $q_N$) prefix of $\phi$. Such an initial motion has to
reflect in some way in any complexity notion, although the search for $q_N$
does not contribute anything to the actual computation on it.
Granting a machine access to individual information encoded through $\phi$
(black-box approach) without charging too much for such access can be realized
by oracle Turing machines (oracle machines, or OTMs, for short).

Recall that an oracle machine is a classical (possibly multi-tape) Turing
machine with the addition of a special query tape and two new states: One to
initiate the query to the oracle with the content of the question written on
the query tape,
and a second to mark that the oracle has written its respective answer on
the query tape. The oracle attached to a machine can either be a subset of
$\Sast$ (a possibly undecidable decision problem), or a string function.
We choose the latter type, a function-oracle machine model
(cf. <cit.>).

* A second-order representation $\reptpl$ of a set $X$
is a partial surjective function $\reptpl \parcol \Baire \to X$.

* Any ordinary representation $\reptpl \parcol \Cantor \to X$
(, in the sense of <ref>)
induces a second-order representation $\tilde{\reptpl}$:
Any $\reptpl$-name $\phi = (b_i)_i$, $b_i \in \Sigma$,

yields a $\tilde{\reptpl}$-name $\tilde{\phi}$ through
$\tilde{\phi}(s) \dfeq b_{\len{s}}$ for any $t \in \Sast$.
[The reader is referred to <cit.> for
more (formal) definitions and extensions of second-order

* Second-order representations $\tilde{\reptpl}_1$ and
$\tilde{\reptpl}_2$ of $X_1$ and $X_2$, respectively, induce a
second-order representation
$\tilde{\reptpl}_1 \times \tilde{\reptpl}_2$
of $X_1 \times X_2$:
If $\phi_i$ is a $\tilde{\reptpl}_i$-name of $x_i \in X_i$, then
$\enc{\phi_1,\phi_2}_{\Baire}$ is a $\tilde{\reptpl}_1 \times \tilde{\reptpl}_2$-name of $X_1 \times X_2$.

Functions computable by oracle machines can be defined over realizers similar
to <ref>.

Assume $\reptpl$ and $\reptpl'$ to be second-order representations of $X$
and $X'$, respectively, and let $f \parcol X \to X'$ be some function.

* A function $g \parcol \Baire \times \Sast \to \Sast$ is computable
by an oracle machine $M^?$ if for all
$(\phi,s) \in \Baire \times \Sast$,
$M^\phi$ started with $s$ halts and writes $g(\phi,s)$ on its
output tape.

* A function $g \parcol \Baire \times \Sast \to \Sast$ is called a
$(\reptpl,\reptpl')$-realizer of function $f$ if for all
$\phi \in \reptpl^{-1}\big[ \dom(f) \big]$,
$(f \circ \reptpl)(\phi) = \reptpl'\big( g(\phi,\cdot) \big)$
holds true. (Note that $g(\phi,\cdot) \in \Baire$.)

* Function $f$ is called $(\reptpl,\reptpl')$-computable if it has
a $(\reptpl,\reptpl')$-realizer computable by some oracle machine.

§.§.§ Relation between both models.

Although the type-2 machines on one hand side and oracle machines on the
other are seemingly different approaches to Real Computability, they
are actually computably identical.

Let $\reptpl$ and $\reptpl'$ be ordinary representations of $X$ and $X'$,
respectively. Every $(\reptpl,\reptpl')$-computable (-continuous) function
(, realized by some type-2 machine computable function)
$f \parcol X \to Y$ is also $(\tilde{\reptpl},\tilde{\reptpl}')$-computable
(-continuous) (, realized by some oracle machine computable function);
and vice versa.

This follows by type conversion <cit.>: Since $f$ is
$(\reptpl,\reptpl')$-computable (-continuous), it has some computable
(continuous) realizer $g \parcol \Cantor \to \Cantor$. By the aforementioned
Lemma, a function $G \parcol \Cantor \times \Sast \to \Sast$,
$(\reptpl,\reptpl')$-computable by some type-2 machine, exists such that the
following hold true:

* Function $G$ has a suitable domain: for all $\phi \in \Cantor$,
$\phi \in \dom(g)$ if $\xall{s}{\Sast} (\phi,s) \in \dom(G)$;

* and $G$ does behave like $g$ (extensionally):
$\xall{\phi}{\dom(g)} \xall{s}{\Sast} G(\phi,s) = g(\phi)(s)$.

Since $G$ is computable by some type-2 machine, it is computable by some
oracle machine as well, thusly $(\tilde{\reptpl},\tilde{\reptpl}')$-realizing
$f$. The reverse direction follows similarly when used that representations
in TTE can equivalently written stated over $\Baire$ instead of $\Cantor$

From now on we omit the “tilde” and simply write “$\reptpl$” whenever we
reason about second-order representations $\tilde{\reptpl}$. Arguments
$s \in \Sast$ of names $\phi$ are usually of form $s = \enc{q,0^n}$ for a
dyadic point $q \in \ID^d$ and a precision parameter $n \in \IN$. We use
$\phi(q,0^n)$ as a shorthand for the correct but more verbose
$\phi \big( \tuple{\dyadicrep[d](q),\unatrep(n)} \big)$.

§.§ Second-order representations of sets

Throughout this paper, we solely concentrate on closed non-empty
subsets of $\IR^d$ (for various $d$) and subclasses thereof.
More precisely:
In any dimension $d \in \IN$ we denote the class of closed non-empty
subsets of $\IR^d$ by $\closedset[d]$, the class of compact subsets by
$\compset[d] \dfeq \st[0]{S \in \clset[d]}{
\xusome{\delta > 0} S \subseteq \clb{0}{\delta}}$,
convex subsets are in
$\convset[d] \dfeq \st[0]{S \in \clset[d] \cap (\IR^d,\ndot[2])}{
\xall{x,y}{S} \xall{\lambda}{[0,1]} \lambda x + (1-\lambda)y \in S}$, and
regular subsets in
$\regset[d] \dfeq \st[0]{S \subseteq \clset[d]}{\ol{\inner{S}} = S}$.[
Normed vector spaces over equivalent norms are homeomorphic, thus imply
the same topology.
It therefore is not necessary to tie any of these subclasses (except for
$\convset$) to a concrete norm.
All notions are depicted on <ref>.

Classes of subsets of Euclidean space:
Closed $\closedset$,
compact $\compset$,
convex $\convset$, and regular $\regset$.

Intersections of the above subclasses will also be of interest, ,
the class $\KR[d] \dfeq \compset[d] \cap \regset[d]$ of bounded bodies;
understand $\CR[d]$ (convex bodies), $\KC[d]$, and $\KCR[d]$
(bounded convex bodies) similarly.
Omitting the dimension on any class of subsets denotes the union over all $d$,
, $\clset \dfeq \bigcup_{d \in \IN} \clset[d]$ and so forth.

For a set $S \in \closedset[d]$ and a norm $\normdot$ we define
the distance function $\dist[\normdot]{S} \colon \IR^d \to \IR_{\geq 0}$,
mapping any point $q \in \IR^d$ to its minimal distance to set $S$,
by $\dist[\normdot]{S}(q) \dfeq \min_{x \in S} \norm{q - x}$.

Every representation for sets attempts to answer specific questions about the
respective set it encodes: Given a point $x$ and a set $S$, is $x \in S$? If
not, is $x$ far off of $S$? How far is it off?

From <ref> we can infer that only trivial sets $S$ (,
$S = \emptyset$ or the whole space, $S = \IR^d$) are representable by their
characteristic functions since they are discontinuous in all other cases.
We thus have to allow any name $\phi$ of a reasonable representation of closed
sets to make errors somewhere if $\phi$ represents $S \in \closedset[d]$ with
$\emptyset \subset S \subset \IR^d$. This error, however, has to be
controllable through a precision parameter $n$,

just like for reals and functions.

Subsequently, we cite five different definitions (visualized in
<ref>) for representations of sets.

Representations of sets: Illustration of <ref>

Fix a dimension $d \in \IN$ and a norm $\normdot$ on $\IR^d$. Points $q$
are chosen from $\ID^d$, and precision parameters are denoted by
$n \in \IN$.

* Weak-membership representation:
A $\wrtn{\wmemrep[d]}{\ndot}$-name $\phi$ of $S \in \regset[d]$

* $\phi(q,0^n) = 1$ if $\cball_{\normdot}(q,2^{-n}) \subseteq S$
(, $q$ lies $2^{-n}$-deep within $S$), or

* $\phi(q,0^n) = 0$ if $\cball_{\normdot}(q,2^{-n}) \cap S = \emptyset$
(, $q$ is off by more than $2^{-n}$).

* A $\wrtn{\gridrep[d]}{\normdot}$-name $\phi$ of $S \in \compset[d]$

* $b \dfeq \uintrep^{-1}(\phi(\eword))$ is an upper bound on the
size of $S$, , $S \subseteq \cball_{\ndot}(0,2^{b})$, and

* $\phi$ encodes a sequence of sets $B_n \subset \ID^d_n$ through
$\phi(q,0^n) = \chi_{B_n}(q)$ that is $2^{-n}$-close to $S$ in the
Hausdorff-distance $\dH$, ,
$\dH\left( B_n, S \right) \leq 2^{-n}$:

$\xall{n}{\IN} \xall{x}{S} \xsome{q}{B_n}
\vnorm{q-x} \leq 2^{-n}$, and

$\xall{n}{\IN} \xall{q}{B_n} \xsome{x}{S}
\vnorm{q-x} \leq 2^{-n}$.

* A $\wrtn{\setrep[d]}{\normdot}$-name $\phi$ of $S$ satisfies

* $\phi(q,0^n) = 1$ if
$\ball_{\normdot}(q, 2^{-n}) \cap S \neq \emptyset$
($q$ is $2^{-n}$-close to $S$), or

* $\phi(q,0^n) = 0$ if $\cball_{\normdot}(q, 2^{-n+1}) \cap S = \emptyset$
($q$ is at least $2^{-n+1}$-far off of $S$).

* A $\phi \in \Baire$ is a $\wrtn{\distrep[d]}{\normdot}$-name of
$S \in \clset[d]$

whenever $\phi$ encodes $S$' distance function, ,
$\abs[0]{ \phi(q,0^n) - \dist[\normdot]{S}(q) } \leq 2^{-n}$.

* Relative version of $\distrep[d]$ (specialization of

A $\phi \in \Baire$ is a $\wrtn{\reldistrep[d]}{\normdot}$-name of
$S \in \clset[d]$ if for all $q \in \ID^d$ and $n \in \IN$,
$\phi$ satisfies

\begin{align} \label{eqn:def-reldistrep}
%	\xall{q}{\ID^d}
%	\xall{n}{\IN}
3/4 \cdot \dist[\normdot]{S}(q) - 2^{-n}
\leq \phi(q,0^n)
\leq 5/4 \cdot \dist[\normdot]{S}(q) + 2^{-n}.
\end{align}

§.§.§ A few historical remarks.

The concept underlying $\distrep$ (representation of the distance function;
cf. <cit.>) is the same as for
Turing located sets (<cit.>; dating even back to Brouwer
and the concept of recognizable sets <cit.> is
underlying the weak membership problem/representation $\wmemrep$
(<cit.>; also in <cit.>).
A strengthening of $\wmemrep$, where the positive information is exact
(in the sense that condition “$x$ is $2^{-n}$-close to $S$” is replaced
with “$x \in S$”), was also considered under the notion of strong
recognizability <cit.> and revisited later as
weak computability by <cit.>.
Although Chou/Ko seemed to be the first to formally present this
strengthening, this concept of one-sided error also has already been present
implicitly as part of <cit.>.
Representation $\gridrep$ was defined and used  in
<cit.>, <cit.>;
and $\setrep$ in <cit.>,

Questions regarding both the computability of sets different
representations (which, however, are not part of this work) and the
computability relation of representations (which are and will be
discussed to some extent in <ref>) has been covered in many
articles (see, ,

§.§ Enrichments

The representations we have seen in the previous section are rather generic.
In practice, however, additional parameters are usually known, , bounds on
diameters of sets or rate of growth of functions.
Such additional discrete information (discrete advice parameters, or
just advice parameters for short <cit.>) may be
uncomputable from a given representation, but will turn out to be of
great use (complexity-wise) in

Let $\sastrep \parcol \Baire \to \Sast$ denote a representation of $\Sast$.
Further, let $\reptpl \parcol \Baire \to X$ be a representation of a set $X$,
and $\ens{E} \dffn X \mto \Sast$ a multi-valued function (encodes information
$\reptpl$-names are enriched with).
Then $\phi$ is a $\reptpl \enp{E}$-name of $x \in X$ if it is of form
$\phi = \enc{\phi_1,\phi_2}$ with $\reptpl(\phi_1) = x$ and
$\sastrep(\phi_2) \in \ens{E}(x)$.

More specific, we use the following four concrete enrichments in the remainder
of this paper.

* Outer radii:
Consider the enrichment

\[
\ens{b} \dffn \compset[d] \mto \Sast
\eqnsp , \quad
\ens{b} \dffn S \mmapsto \st{ \uintrep(b) }{
b \in \IZ \text{ and } S \subseteq \cball_{\ndot}(0,2^b) }
\]

By definition, $\setrep[d]|^{\compset} \enp{b}$ then is a representation
of $\compset[d]$ whereby each name contains an outer radius parameter
$b$ (encoded in unary according to $\ens{b}$) on the encoded compact set.
We refer to $2^b$ as an outer radius the outer radius parameter

* Inner radii and inner points:
In a similar fashion to $\ens{b}$ define enrichments

r [d] ,         	r .3ex S  (r)
r ∈,  xS _(x,2^-r) ⊆S

a [d] ,         	a S [1] [d](a)
a ∈^d ,  δ> 0 _(a,δ) ⊆S

We refer to decoded images under $\ens{r}$ as inner radii parameter
(giving an inner radius of $2^{-r}$),
and to decoded images under $\ens{a}$ as inner points.

* Information encoded by $\ens{a}$ and $\ens{r}$ is independent of the
other, , the bound on an inner radius parameter due to $\ens{r}$ has
not to correspond to the existing around the inner point due to $\ens{a}$.
If we need both information, , an inner ball, then we combine
it to

\[
\ens{ar} \dffn S \in \regset[d] \mmapsto
\st[1]{ \enc[1]{\dyrep[d](a), \uintrep(r)} }{
\ball_{\ndot}(a,2^{-r}) \subseteq S}
\eqnsp .
\]

These choices of encodings also meet both theory and practice: cf., for
example, <cit.> and <cit.>.
Note that both the dimension and the norm will be always understood from the
context and therefore does not reflect in the notation of any enrichment.

The correct way to work with enriched representations would be like this:
Let $\ens{E}$ be an enrichment, and $\enc{\phi_1,\phi_2}$ be a
$\reptpl \enp{E}$-name.
Then $E \dfeq \sastrep(\phi_2)$ is a concrete instance of
enrichment $\ens{E}$ of object $x \dfeq \reptpl(\phi_1)$.
As this intermediate step of “extracting” $E$ from $\enc{\phi_1,\phi_2}$
is just a technical though necessary detail which does not add to any proof
argument, we use the typographical convention to denote a concrete decoded
instance of $\ens{E}(x)$ “variable style”, that is, as $E$.
In the above spirit, further abbreviate a
$\reptpl[d]|^{\KR} \enp{a} \enp{r} \enp{b}$-name
$\enc{\phi_1,\phi_2,\phi_3,\phi_4}$ by $\enc{\phi_1,a,0^r,0^b}$.
This notation has been purposefully chosen as a reminder that

* inner points as advice parameters are encoded in binary, while

* both inner and outer radii are encoded in unary according to
enrichments $\ens{r}$ and $\ens{b}$, respectively.

§.§ Complexity of functions and operators: upper and lower bounds

We briefly recap some facts from discrete complexity theory.
Assume $M$ to be a Turing machine that either accepts its input $s \in \Sast$
or rejects it; , $M$ always terminates. The computation time of such a
machine $M$ is bounded by some non-decreasing function $t \colon \IN \to \IN$
(or: $t$-time bounded) if for all $s \in \Sast$, $M$ started on $s$ holds
within $t(\len{s})$ steps.

Unless stated otherwise, we use “Turing machine” as a synonym for
“deterministic Turing machine”. Allowing a machine also to
guess strings from $\Sast$ makes it non-deterministic.
Through the course of this paper we need three complexity classes:
$\PTime$ marks the class of all problems $A \subseteq \Sast$ decidable by a
deterministic polynomial-time bounded Turing machine, and $\NPTime$ the class
of problems decidable by a non-deterministic polynomial-time Turing
Decision problems $A \in \NPTime$ can equivalently be stated as being
polynomial-time verifiable by a deterministic Turing machine; ,
there exists a decision problem $A' \subseteq \Sast$ which is polynomial-time
equivalent to $A$ and satisfies $\xsome{B}{\PTime} A' = \st[0]{s \in \Sast}{
\xsome{w}{\Sigma^{\len{s}}} \enc{w,s} \in B}$.
Given an $s \in \Sast$, a $w$ which verifies $\enc{w,s} \in B$ is
usually called a witness for $s \in A'$.

The class $\UPTime$ contains problems $A \subseteq \Sast$ decidable by an
unambiguous non-deterministic polynomial-time Turing machine; that is,
a machine that for each $s \in A$ has exactly one accepting path.
It is easy to see that $\PTime \subseteq \UPTime \subseteq \NPTime$, but
whether any of these inclusions is proper is a wide-open problem. We defer
the discussion of the hypothetical case $\PTime \neq \UPTime$ and its
implications until <ref>.

As for example pointed out in <cit.>, problems usually come
with a variety of structural information (like the number of nodes in a graph,
number of variables in a formula, number of faces of a polyhedron), which
however is not reflected in the above one-ary notion of complexity.
Parameterized complexity extends upon that:
A parameterized decision problem $(A,k)$ ($A \subseteq \Sast$ with
parameterization $k \colon \Sast \to \IN$, which typically is required to be
at least computable) is $(\tau,t)$-time computable, iff a deterministic Turing
machine $M$ exists whose computation time is bounded by
$\tau(k(s)) \cdot t(\len{s})$ for all $s \in \Sast$. If $t$ moreover is a
polynomial, then $(A,k)$ is said to be parameterized polynomial-time
decidable (also: fixed-parameter tractable).

§.§.§ Time complexity.

The complexity notion for oracle machines is similar to that for classical
Turing machines, except for the extension that it takes the oracle in total
one step to read the content written on the oracle tape and to produce its
answer. The computation time of an oracle machine $M^\phi$ (and thus the
complexity of the element of $\Baire$ it computes) with set-oracle (or
equivalently a function-oracle $\phi \in \Cantor$) can solely be measured in
the length of the discrete input given to $M^?$; which is the case for
representations $\wmemrep$, $\gridrep$ and $\setrep$.

Let $t \colon \IN \to \IN$ be some non-decreasing function.

* A function $g \parcol \Cantor \times \Sast \to \Sast$ is $t$-time
computable if an oracle machine $M^?$ exists which for all
$\phi \in \Cantor$ and $s \in \Sast$ computes $g(\phi,s)$ in time
bounded by $t(\len{s})$.

* Let $\reptpl$ and $\reptpl'$ be a second-order representations of
sets $X$ and $X'$, respectively, and let
$\dom(\reptpl) \subseteq \Cantor$.[
That is, $\reptpl$-names are predicates.]
A $(\reptpl,\reptpl')$-computable function $f \parcol X \to X'$ is
$t$-time computable if it is realized by a $t$-time
$(\reptpl,\reptpl')$-computable function
$g \parcol \Cantor \times \Sast \to \Sast$.

As hinted prior to the definition, it is not that obvious how to define
complexity in case of names $\phi$ from $\Baire$ instead of $\Cantor$.
The problem with names from $\Baire$ is that oracle answers in general are
not bounded in the length of its argument as it has been the case for
$\phi \in \Cantor$.

However, combining enrichments with <ref> allows us to
define time bounds whenever the oracle answers can be bounded in terms of the
parameters a representation has been enriched with.
For that purpose, force both $\distrep[d]$- and $\reldistrep[d]$-names $\phi$
to additionally satisfy $\phi(q,0^n) \in \ID^d_{n+1}$.[
Note that the latter condition is only added to prevent unnecessarily
long answers as they are not more accurate (with respect to the conditions
on $\distrep$- and $\reldistrep$-names) when provided with a precision
much higher than $n$.
This restriction is not necessary in the general theory of
second-order polynomials and second-order polynomial-time,
but we defer this discussion until <ref>.]

The subsequent definition is based on <cit.>.

Let $\reptpl$ and $\reptpl'$ be second-order representations of sets $X$
and $X'$, respectively, and $\ens{E} \dffn X \mto \Sast$ an enrichment of $X$.
Moreover, let $\tau, t \dffn \IN \to \IN$ be non-decreasing functions.

* A function $f \parcol X \to X'$ is $(\tau,t)$-time
$(\reptpl \enp{E},\reptpl')$-computable if it has a
$(\reptpl \enp{E},\reptpl')$-realizer
$g \parcol \Baire \times \Sast \to \Sast$ such that the computation time
of $(\phi,s) \in \dom(\reptpl) \times \Sast \mapsto g(\phi,s)$ is bounded
by $\tau\big( \len{\ens{E}(\reptpl(\phi))} \big) \cdot t(\len{s})$.
[Notice the term “$\ens{E}(\reptpl(\phi))$” in the time bound:
Enrichments are by definition multi-valued but $\tau$ is not set-valued.
Although technically incorrect, the meaning “this bound has to hold
true for every advice parameter in $\ens{E}(...)$” clearly is
supported by this notation while the correct statement would be
“the computation time has to be bounded by
$\tau(\len{E}) \cdot t(\len{s})$
for all $E \in \ens{E}(\reptpl(\phi))$”.]

* If $t$ is a polynomial, then $f$ is said to be parameterized
polynomial-time $(\reptpl \enp{E},\reptpl')$-computable.

* If both $t$ and $\tau$ are polynomials, then $f$ is said to be
fully polynomial-time $(\reptpl \enp{E},\reptpl')$-computable.

As advice parameters are part of a name anyway, we simply speak about
“polynomial time” whenever “fully polynomial-time” is meant.
This identification is justified as fully polynomial-time and unparameterized
polynomial-time coincide for $\ens{E} \dffn x \mmapsto \{\eword\}$.

On compact sets $K \in \compset[d]$, this definition allows to bound the
answer lengths in terms of an outer radius parameter $b$ as in
Take representation $\distrep$ as an example:
Assume $\phi \dfeq \enc[1]{\phi',0^b}$ to be a $\distrep[d] \enp{b}$-name of $K$.
Then $\len{\phi'(q,0^n)}$ can be bounded linearly in
$\abs{b} + \len{\enc{q,0^n}}$ for all $q \in \ID^d$ and $n \in \IN$.

§.§ Common proof arguments

We review two common arguments that allows us to prove lower bounds for or
even the uncomputablitiy of operations.

§.§.§ Adversary argument.

The adversary method is used to prove uniform non-subexponential
lower bounds of operators.

Let $\reptpl$, $\reptpl'$, $X$, $X'$ and $f$ as in the former subsections.

Proving lower bounds then goes as follows: For any discrete argument
$s \in \Sast$, pick an element $x \in X$ and construct a subset $Y \subset X$
of cardinality at least exponential in $\len{s}$ for which every item $y \in Y$
only differs slightly from $x$. Argue that in order to differentiate any
$\reptpl$-name $\phi$ for $y$ from one for $x$, any hypothetical machine $M^?$
that $(\reptpl,\reptpl')$-realizes $f$ necessarily has to ask exponentially
many queries to $\phi$.

This approach is similar to the adversary method from Information-Based
Complexity <cit.> where computations are exact, but only finite
information is known about the input. As an example, take Riemann
integration, done on $2^n$ many sampling points in order to achieve an
approximation which is always guaranteed to be within error $2^{-n}$.

§.§.§ Topological discontinuity.

Given second-order representations $\reptpl$ and $\reptpl'$ of sets $X$ and
$X'$, respectively, and a function $f \parcol X \to X'$. By <ref>
we already know that $f$ is not $(\reptpl,\reptpl')$-computable whenever it is
not $(\reptpl,\reptpl')$-continuous. Recall that $\Baire$ comes equipped with
the product topology, providing a way to prove the latter:
Construct an $x \in X$ and an
appropriate $\reptpl$-name $\phi$. Any machine for a hypothetical
$(\reptpl,\reptpl')$-realizer for $f$ does only inspect finitely many values
of $\phi$. Now pick a slightly different $\reptpl'$-name, say $\phi'$, for a
different value, say $x'$, which coincides with $\phi$ on values observed by
$M^?$, but leads it to produce an answer exceeding the prescribed error bound.

§ COMPARING REPRESENTATIONS OF SETS

In this section we compare the representations introduced in
<ref> by means of their polynomial-time
Two aspects will play a key role in these comparisons:
Whether a representation $\reptpl$ is norm-invariant,
, if $\wrtn{\reptpl}{\ndot}$ and $\wrtn{\reptpl}{\ndot'}$ are
polynomial-time equivalent,
and the influence of the dimension parameter.

Both together will prove $\distrep[d]$ to be richer (intuition: to
carry more information) than all of the other representations from
dimension $d=2$ onward by combining that

* $\distrep[d]$ is not norm-invariant for $d \geq 2$,

* all of the other representations we discuss are norm-invariant,

* $\distrep$ reduces to all of the other representations in polynomial

Representation $\wmemrep$, on the other hand, will prove to be poorer
than all of the other representations.
However, this gap between $\distrep$ and $\wmemrep$ can be closed by
restricting to $\KCR$, adding parameters to $\wmemrep$ and applying techniques
from discrete optimization (<ref>), which proves all
representations to be polynomial-time equivalent in this particular setting.

We now turn to the formalization of what has been described above.

Let $\reptpl$ and $\reptpl'$ be representations of the same set $X$.
Then $\reptpl$ uniformly translates (or: reduces) to
$\reptpl'$ $\reptpl \preceq \reptpl'$ for short if
$\id_X$ is $(\reptpl,\reptpl')$-computable.
If $\id_X$ is parameterized polynomial-time $(\reptpl,\reptpl')$-computable,
then we write $\reptpl \parampleq \reptpl'$.
If $\id_X$ is even fully polynomial-time $(\reptpl,\reptpl')$-computable,
then we write $\reptpl \pleq \reptpl'$.

Note that while the notation $\reptpl \preceq \reptpl'$ makes sense when read
as “$\reptpl$ translates to $\reptpl'$”, it is counter-intuitive when read
as a reduction:
$\reptpl$ reduces to $\reptpl'$ if $\reptpl$-names carry
more information than $\reptpl'$-names; hence, $\reptpl$-names are
harder to compute than $\reptpl'$-names.
Reductions in classical complexity theory are usually thought the other way
around, , the harder problem being “greater or equal” to
easier problems.

The intuition about representations encoding more or less information
also explains the following fact which we will use in many places throughout
this paper.

Let $\reptpl_1,\reptpl_2$ be representations of $X$, and
$\reptpl'_1,\reptpl'_2$ be representations of $X'$.
Then every $(\reptpl_1,\reptpl'_1)$-computable function is also
$(\reptpl_2,\reptpl'_2)$-computable whenever $\reptpl_2 \preceq \reptpl_1$
(providing potentially more information about the input) and
$\reptpl'_2 \preceq \reptpl'_1$ (requiring potentially less information
about the output) hold. The same applies if $\preceq$ is replaced with $\pleq$.

For $Y \subseteq X$ let $\reptpl \preceq^Y \reptpl'$ be an abbreviation for
$\reptpl|^Y \preceq \reptpl'|^Y$. This new representation
$\reptpl|^Y \parcol \Baire \to Y$ is the result of the restriction of
$\reptpl$'s image to $Y$.
Apply the same to $\pleq$, $\pless$, $\equiv$ and $\pequiv$.

§.§ Technicalities

There are two technicalities we have to take care of before we can compare
representations by means of $\pleq$:
Norms on $\IR^d$ that lead to well-defined representations,
and the benefits of allowing integer precisions instead of naturals only.
The former leads to the notion of well-behaved norms, while the latter
introduces scale-invariant representations.

§.§.§ Restriction to well-behaved norms.

Representations $\setrep$, $\gridrep$ and $\wmemrep$ depend on the notion of
“being close”.
Practically speaking, a point $q$ gets printed on the screen whenever
$\cball_{\normdot}(q,2^{-n})$ meets the represented set, where points $q$
were chosen from $\ID^d_n$.
The implicit assumption underlying all representations from
<ref> is compatibility with the grid
The whole space, say $X$, can be covered with $\normdot$-balls with radii
$2^{-(n+c)}$ and centers from $X \cap \ID^d_n$, where $c \in \IZ$ is a
contant depending on the pair $\ndot, \ndot[\infty]$.
As an example, take $\normdot \dfeq 4 \cdot \normdot[\infty]$ with
$c \dfeq -\lb{4}$.

The implied necessity to incorporate a norm-dependent constant $c$ into
precision parameters is cumbersome and we avoid it by imposing
the above mentioned “compatibility” on the respective norm.
For the same reason we disallow slanted (or otherwise distorted) norms
like $\norm{(x_1,x_2)} \dfeq (\abs{x_1/2}^2 + \abs{x_2}^2)^{1/2}$ although
this restriction can be avoided (as we will see in <ref>) and
is only up to the author's personal taste.

We denote such norms satisfying both of the above motivated properties as
being well-behaved.

A norm $\normdot$ on $\IR^d$ is said to be well-behaved if it has
the following two properties:

* $\ndot$ is invariant under 90-degree rotations.
More precisely:
Let $\{e_1,\dots,e_d\}$ be the canonical basis of $\IR^d$.
Then $\norm{e_i} = \norm{e_j}$ for all $1 \leq i,j \leq d$.

* $\ndot$-balls are not too small, ,
$\cball_{\ndot[\infty]}(q,2^{-(n+1)}) \subseteq \cball_{\ndot}(q,2^{-n})$
for all $n \in \IN$ and $q \in \ID^d_n$.

It then follows by the second condition that $\IR^d$ can be covered by
$\ndot$-balls with centers from $\ID^d_n$ and radii $2^{-n}$.
Examples of well-behaved norms include the $p$-norms
$\norm[p]{(x_1,\dots,x_d)} \dfeq (\abs{x_1} + \cdots + \abs{x_d})^{1/p}$
for $p \geq 1$, while
$\norm{(x_1,x_2)} \dfeq (\abs{x_1/2}^2 + \abs{x_2}^2)^{1/2}$
(violates the first condition) and
$3/2 \normdot[1]$ (violates the second condition) are not.

For the rest of this paper, we only consider well-behaved norms unless
stated otherwise.

§.§.§ Scale-invariance.

Starting with <cit.>, complexity results were stated for functions
whose domains were a subset of the unit hypercube; the same was true
for sets. This restriction rendered (at least for sets) the question about
precision parameters smaller than $0$ (, absolute error bounds $>
2^{-0}$) pointless, which allowed for a complexity notion solely in the
precision parameter.

However, as we will see many times in <ref>,
algorithms for operators on sets often involve an unavoidable preprocessing
step (given the representations we have seen so far):
Given $b \in \IN$, chop $\clb[\normdot[\infty]]{0}{2^b}$ into $2^{d(b+1)}$
unit hypercubes,
pick a subset of them (usually one cube), then proceed by applying the
given $\reptpl$-name to this subset.
It is this preprocessing step which seems to be artificial and superfluous
as the real algorithm often starts only after this step.

For this reason the author believes that a closed subset $S$ of $[0,1]$ (or
any fixed compact set) should admit, up to a polynomial rather than
exponential in $k$, the same complexity as $S$ inflated by a factor of $2^k$.
Both sets are still structurally the same!

To this end, let $\sisetrep$ be the extension (or: relaxation) of
representation $\setrep$ to integer precisions, ,
a $\sisetrep[d]$-name $\phi$ satisfies

\[
\phi(s) = 1
\text{ if } S \cap \opb{q}{2^{-n}} \neq \emptyset
\eqnsp ; \qquad
\phi(s) = 0
\text{ if } S \cap \clb{q}{2^{-n+1}} = \emptyset
\eqnsp .
\]

with $s \dfeq \enc[1]{\dyrep[d](q),\uintrep(n)}$.
Recall that we agreed to equivalently write $s$ as $\enc[1]{q,0^n}$ where
$0^n$ abbreviates the “unary encoding” of integer $n$.

With the following Lemma we attempt to provide a way around the above
described dilemma.

* Scaling a closed set by factor $2^{k}$ for $k \in \IZ$ is a
parameterized polynomial-time operation in the absolute value
of $k$ (cf. <cit.>), that is,
the binary length of $2^k$.
More precisely:
Operator $\opname{Scale} \dffn (S,k) \mapsto \st[0]{2^k x}{x \in S}$ is
$(\setrep[d] \times \uintXrep, \setrep[d])$-computable in parameterized
polynomial time.

* In contrast,

$\opname{Scale}$ is fully polnomial-time
$(\sisetrep[d] \times \uintXrep, \sisetrep[d])$-computable.

* $\setrep[d] \parampleq \sisetrep[d] \pleq \setrep[d]$.

The first statement follows by the argument hinted prior to this Lemma:
Let $q \in \ID^d$ and $n \in \IN$.
If $n-k \geq 0$, then simply query the $\setrep[d]$-name with
$\enc{2^k q,0^{n-k}}$.
If $n-k < 0$, then first split $\cball(2^k q, 2^{k-n})$ into unit-balls and
combine the queries on the center and precision $0$ on each of these balls.

For the second statement, use the argument from the above first case, namely,
query the $\sisetrep[d]$-name with precision $n-k$.

The first reduction in statement three follows immediatiely from 1. and 2.
For the second reduction, use the split of $\cball(2^k q,2^{k-n})$ into
unit-balls and argue as in the first case of statement one.

It follows by the previous statement that all scaled versions of a set
are polynomially equivalent with respect to $\sisetrep$.

As the concept of a scale-invariant representation avoids the above described
deficiencies, we like to impose it on every representation $\reptpl$
from <ref>.
Therefore, we from now like $\widehat{\reptpl}$ to be understood as the
scale-invariant version of $\reptpl$, and then associate $\reptpl$ with
$\widehat{\reptpl}$ (, drop the explicit hat).
As a consequence, precision parameters shall now usually be integers.

§.§ Topological versus computable equivalence of norms

In this section we examine the question which representations $\reptpl$ are
norm-invariant, , whether
$\wrtn{\reptpl}{\ndot} \pequiv \wrtn{\reptpl}{\ndot'}$ holds true for
all topological equivalent well-behaved norms $\ndot, \ndot'$.

Notice that “norm-invariance” inherently asks about polynomial-time
norm-exchange is a computable operation for all representations from

Our first result generalizes Braverman's remark
<cit.> on the interchangeability of
$\wrtn{\setrep}{\normdot[2]}$ and $\wrtn{\setrep}{\normdot[\infty]}$.

$\wrtn{\setrep[d]}{\normdot} \pequiv \wrtn{\setrep[d]}{\normdot'}$
holds in any dimension $d \in \IN$ and for any two norms
$\ndot,\ndot'$ on $\IR^d$.

The key to prove this proposition is its non-uniformity any two
well-behaved norms $\normdot,\normdot'$:
The necessary information (here: the “coverage pattern” of the unit
$\normdot'$-ball) for a machine to translate from
$\wrtn{\setrep[d]}{\normdot}$ to $\wrtn{\setrep[d]}{\normdot'}$ can be
directly encoded into it.

For every two norms $\ndot,\ndot'$ on $\IR^d$ exists a constant $k \in \IN$
and a finite set $D \subset \ID^d_k$ (“coverage pattern”) such that

\[
\cball_{\ndot'}(0,1)
\subseteq
\bigcup\nolimits_{p \in D} \cball_{\ndot}(p,2^{-k})
\subseteq
\cball_{\ndot'}(0,3/2)
\eqnsp .
\]

Note that $\ndot'$ can only be approximated by $\ndot$-balls up to a
constant factor by the above coverage pattern $D$.
Approximating the shape of a $\ndot'$-ball up to arbitrary precision,
however, might still be uncomputable.

Let $k \in \IN$ and $\ID^d_k$ as in <ref>.
Let further $\phi$ be a $\wrtn{\setrep[d]}{\ndot}$-name of $S \in \clset[d]$,
$q \in \ID^d$, and $n \in \IZ$.
Claim: $\phi'$, defined as

\[
\phi'(q,0^n) \dfeq \max_{p \in D} \phi(p', 0^{n+k})
\eqnsp , \quad
p' \dfeq q + 2^{-(n+k)} p
\eqnsp ,
\]

is a $\wrtn{\setrep[d]}{\ndot'}$-name of $S$.
Note that since $D$ is finite, the maximum ranges only over finitely many
values and is therefore computable in time linear in $n + k + \len{\enc{q}}$.

If $\ball_{\ndot'}(q,2^{-n}) \cap S \neq \emptyset$, then by
<ref> there exists a point $p_0 \in D$ such that
$\cball_{\ndot}(p',2^{-(n+k)})$ meets $S$, justifying
$\phi'(q,2^{-n}) = 1$.
If, on the other hand, $\cball_{\ndot'}(q,2^{-n+1}) \cap S = \emptyset$, then
in particular $\cball_{\ndot}(p',2^{-(n+k)}) \cap S = \emptyset$ for all
$p \in D$.
Their union covers $\cball_{\ndot'}(q,2^{-n})$ which renders
$\phi'(q,2^{-n}) = 0$ to be correct.

Neither one of the norms has actually to be computable a direct
consequence of the note following <ref>.

The argument from <ref> generalizes to $\wmemrep[d]$
(over $\regset[d]$) and $\gridrep[d]$ (over $\compset[d]$), rendering both
representation to be norm-invariant, too. Representation $\distrep$,
however, turns out to be not norm-invariant not even
non-uniformly (provided $\PTime \neq \NPTime$):

In any dimension $d \geq 2$ there is a set $S \in \compset[d]$ that is
polynomial-time $\wrtn{\distrep[d]}{\normdot[1]}$-computable but not
polynomial-time $\wrtn{\distrep[d]}{\normdot[\infty]}$-computable
if and only if $\PTime \neq \NPTime$.

Only if ($\PTime = \NPTime$ implies that $\distrep$ is
(non-uniformly) norm-invariant).

Suppose $\PTime = \NPTime$ and let $\phi_1$ be a polynomial-time
$\wrtn{\distrep[d]}{\ndot[1]}$-computable name of $S$.
Now consider the sets $N$ and $P$,

\begin{align*}
N & \dfeq \st[1]{ \enc{p,\delta,0^n,0^m} }{
\xusome{p' \in \ID^d_{n+2},\, \phi_1(p',0^{n+2}) \leq 2^{-(n+2)}}
\enc{p,p',\delta,0^n,0^m} \in P }
\eqnsp , \\
P & \dfeq \st[1]{ \enc{p,p',\delta,0^n,0^m} }{
\abs{\delta - \norm[\infty]{p-p'}} \leq 2^{-m} }
\eqnsp ,
\end{align*}

which in turn are polynomial-time decidable by the above assumption.

Search for a $2^{-n}$-approximation $\delta_{n+1}$ to
$\dist[\ndot[\infty]]{S}(q)$ by iteratively determining distances
$\delta_i$ and associated narrowed sets $\Delta_{i+1} \dfeq
\st{x \in [0,1]^2}{\abs{\delta_i-\norm[\infty]{x-q}} \leq 2^{-(i+1)}}$
such that $\delta_i \leq \dist[\ndot[\infty]]{S}(q)$ and
$\xsome{p'(\delta_i)}{\Delta_{i+1} \cap \ID^d_{n+2}}
\enc{q,p'(\delta_i),\delta_i,0^n,0^{i+1}} \in P$.

A $\wrtn{\distrep[d]}{\ndot[\infty]}$-name for $S$ can be recovered from
queries “$\enc{q,\delta_i,0^n,0^i} \in N$?” by the following iterative
procedure (cf. <ref>):
Let $\delta_0 \dfeq 0$.
Then for each $1 \leq i \leq n+1$ set $\delta_i \dfeq \delta_{i-1}$ if
$\enc{q,\delta_{i-1},0^n,0^i} \in N$, and
$\delta_i \dfeq \delta_{i-1} + 2^{-i}$ otherwise.
This way,

\begin{align}
\label{eqn:distrep-if}
\delta_i
\leq \dist[\ndot[\infty]]{S}(q)
\leq \delta_i + 2^{-i} + 2 \cdot 2^{-(n+2)}
\eqnsp ,
\end{align}

and therefore
$\abs{\dist[\ndot[\infty]]{S}(q) - \delta_{n+1}} \leq 2^{-n}$.
We prove the correctness of <ref> by induction.
For $i=0$ it surely is true, so consider the case $i > 0$.
If $\enc{q,\delta_{i-1},0^n,0^i} \in N$, then eqn:distrep-if
holds true for $\delta_{i} \dfeq \delta_{i-1}$ by the construction of $N$.
If, on the other hand, $\enc{q,\delta_{i-1},0^n,0^i} \not\in N$,
then for all $p' \in \ID^d_{n+2}$ with $\phi_1(p',0^{n+2}) \leq 2^{-(n+2)}$
we have $\abs{ \delta_{i-1} - \norm[\infty]{q-p'} } > 2^{-i}$.
Since eqn:distrep-if holds for $\delta_{i-1}$, it firstly
implies $\dist[\ndot[\infty]]{S}(q) > \delta_{i-1} + 2^{-i}$.
But then eqn:distrep-if rewrites as

\[
\delta_{i-1} + 2^{-i}
\leq \dist[\ndot[\infty]]{S}(q)
\leq \delta_{i-1} + 2^{-i+1} + 2^{-n}
\]

which is exactly eqn:distrep-if for
$\delta_i \dfeq \delta_{i-1} + 2^{-i}$.

Consequently, $\phi(q,0^n) \dfeq \delta_{n+1}$ gives a
$\wrtn{\distrep[d]}{\ndot[\infty]}$-name of $S$.

We prove this direction only for $d = 2$, but the generalization to higher
dimensions follows by similar constructions.
Assuming $\PTime \neq \NPTime$, we construct an adversary set $A$ through a
proper encoding of an $\NPTime$-complete problem $N \subset \Sigma^\ast$ of
form $N = \st{s \in \Sigma^\ast}{\xsome{w}{\Sigma^{\len{s}}} \enc{w,s} \in P}$,
$P \in \PTime$, into $A$.
To this end, for $n \in \IN$ and $0 \leq i < 2^n$ associate the $i$-th
string $s \in \Sigma^{n}$ with the set
$A_{n,i} \subset [s_{n,i}, s_{n,i+1}] \times [0,2^{-(2n+1)}]$ where
$s_{n,0} \dfeq 1-2^{-n}$, $s_{n,i} \dfeq s_{n,0} + i \cdot 2^{-(2n+1)}$ and
(just to simplify the notation) $s_{n,2^n} \dfeq s_{n+1,0}$.
For each word $s \in \Sigma^n$ we then split its associated set $A_{n,i}$
into $2^n$ slices $A_{n,i,j}$, $0 \leq j < 2^n$, where $A_{n,i,j}$ is
associated with the $j$-th string $w \in \Sigma^{n}$.
To this end, let $s_{n,i,j} \dfeq s_{n,i} + j \cdot 2^{-(3n+1)}$ and
Whenever $\enc{w,x}$ is in $P$ we code a “bump” in $A_{n,i,j}$, and a
simple line otherwise; , for $w,s \in \Sigma^{n}$,
$A_{n,i,j} \dfeq s_{n,i,j} + 2^{-(3n+1)} \cdot A_{\wedge}$ if
$\enc{w,s} \in P$, and $A_{n,i,j} \dfeq s_{n,i,j} + 2^{-(3n+1)} \cdot A_{-}$
otherwise; $A_{\wedge} \dfeq \st[0]{(x,y) \in [0,1]^2}{
x - y = 0 \text{ for } x \leq 1/2,
\text{ and } x + y = 1 \text{ for } x > 1/2}$,
$A_{-} \dfeq \st[0]{(x,y) \in [0,1]^2}{y = 0}$.
Thus $A \dfeq \bigcup_{n,i,j \in \IN,\, 0 \leq i,j < 2^n} A_{n,i,j}$
encodes $N$.

Encoding a certain $\NPTime$-set $N$ into a
polynomial-time $\wrtn{\distrep[2]}{\normdot[1]}$-computable set $A$
such that $A$ being also polynomial-time
$\wrtn{\distrep[2]}{\normdot[\infty]}$-computable would imply
$\PTime = \NPTime$.

Without further notational overhead associate each point
$q \in \ID^1 \cap [0,1]$ with the (lexicographically) largest triple
of indices $(n,i,j)$ such that $q$ belongs to $[s_{n,i,j},s_{n,i,j+1}]$.
As before, $\enc{w,s}$ is also uniquely identified by this triple.
Now it is easy to construct a $\wrtn{\distrep[2]}{\normdot[1]}$-name
for $A$, while it is hard (, not computable in polynomial time) to
construct one $\wrtn{\distrep[2]}{\normdot[\infty]}$ (both cases are
also sketched in <ref>(b) and
<ref>(c), respectively).

* A $\wrtn{\distrep[2]}{\normdot[1]}$-name $\phi$ of $A$ can be
constructed in polynomial time:

\[
\phi\big( (q_1,q_2), 0^n \big) \dfeq
\abs[1]{
q_2 - \chi_P\enc{w,s} \cdot \big( 2^{-(3n+2)}
- \abs{ q_1 - (s_{n,i,j} + s_{n,i,j+1})/2 } \big)
\]

* Now consider $\wrtn{\distrep[2]}{\normdot[\infty]}$.
Assume there was a polynomial-time OTM $M^?$ which could compute a
$\repnorm{\distrep[d]}{\infty}$-name $\phi'$ for $A$.
Evaluating $\phi'$ at
$(q'_1,q'_2) \dfeq \big(
(s_{n,i,0} + s_{n,i,0})/2,\,
\big)$
with precision $n' \dfeq 3n+4$ then decides $N$ because
$\phi'\big( (q'_1,q'_2), 2^{-n'} \big) \geq 2^{-(2n+2)} - 2^{-(3n+3)}$
if and only if a witness $w \in \Sigma^n$ exists with $\enc{w,s} \in P$.

§.§ Polynomial-time relations

Representations $\setrep[d]$, $\gridrep[d]$ and $\wmemrep[d]$ are
norm-invariant, and $\reldistrep[d]$ will prove to be, too, later in this
Representation $\distrep[d]$, on the other hand, is not norm-invariant
in any dimension $d \geq 2$.
Note that this distinction only holds from the perspective of polynomial-time
reducibility, but disappears for pure computability.
More precisely, representation $\distrep[d]$ has been shown to be
computably equivalent to $\setrep[d]$ in any dimension $d$ if
one restricts both of them to the class of convex bodies $\cb$.
The same is true for the relation of $\wmemrep[d]$ to $\setrep[d]$.

$\distrep[d] \equiv^{\cb} \setrep[d] \equiv^{\cb} \wmemrep[d]$
in any dimension $d \in \IN$.

They are all equivalent because (intuitively speaking) points can be found
due to regularity (regular sets are full-dimensional), and can be checked
(locally) to be of the desired precision due to convexity
(check if all points in a small neighborhood are also contained in the set).

In this section we now systematically compare all representations from
<ref> regarding their polynomial-time reducabilites

* dimension $d=1$ and for $d \geq 2$, and

* over various subclasses of $\clset[d]$.

As a result, representations $\setrep[d] \enp{b}$, $\reldistrep[d] \enp{b}$,
and $\gridrep$ prove to be $\pleq$-equivalent over $\compset[d]$ for every
$d \in \IN$.
Taking $\setrep[d]$ as a representative for this equivalence class,
$\distrep[d] \pless \setrep[d]$ holds true for $d \geq 2$,
and $\setrep[d] \pless \wmemrep[d]$ in any dimension (both even on
$\KCR[d]$!), which leaves us in a very different situation compared to
However: This distinction between $\distrep[d]$ and $\wmemrep[d]$ disappears
when given the right set of additional parameters (<ref>),
yielding one equivalence class of representations for sets as the result.

§.§.§ How representations relate in dimension $d=1$.

$\repnorm{\distrep[1]}{} \enp{b} \pequiv^{\compset}
\repnorm{\reldistrep[1]}{} \enp{b} \pequiv^{\compset}
\repnorm{\setrep[1]}{} \enp{b} \pequiv^{\compset}
\repnorm{\gridrep[1]}{}$,
$\setrep[1] \pleq^{\regset} \wmemrep[1]$,
and $\repnorm{\wmemrep[1]}{} \enp{ar} \pleq^{\cb} \repnorm{\setrep[1]}{}$.

Without loss of generality, let $\ndot \dfeq \ndot[\infty]$.
Notice that the reductions
$\distrep[1] \enp{b}
\pleq^{\compset} \reldistrep[d] \enp{b}
\pleq^{\compset} \setrep[1] \enp{b}
\pleq^{\compset} \gridrep[1]$
already follow by definition of the respective representations.

* Reduction $\setrep[1] \enp{b} \pleq^{\compset} \distrep[1]$:
Let $\enc{\phi,0^b}$ be a $\setrep[1] \enp{b}$-name of a closed
$S \subseteq \cball(0,2^b)$.
Further, set $b' \dfeq \max\{1,b\}$ and $c' \dfeq \lb{\max\{2,\norm{q}\}}$.
For any $q \in \ID$ and $n \in \IZ$, test if $\phi(q,0^{n+1}) = 1$.
If it is, then $0$ is a valid $2^{-n}$-approximation of $\dist{S}(q)$.
If, on the other hand, $\phi(q,0^{n+1}) = 0$, then first find the smallest
$i \in \IN+$, $1 \leq i \leq n+b'+c'+1$, with $\phi(q,0^{n+1-i}) = 1$.
Having found $i$, continue with two binary searches, one in $[q-2^{i-n},q]$
and the other in $[q,q+2^{i-n}]$, for points $p_-,p_+ \in \ID_{n+1}$
eventually satisfying $\phi(p_\pm,0^{n+1}) = 1$ and minimizing
$\norm{q - p_\pm}$.
Then $\min \{ \abs{q-p_-}, \abs{q-p_+} \}$ consitutes a valid
$2^{-n}$-approximation of $\dist{S}(q)$.

* Reduction $\reldistrep[1] \enp{b} \pleq^{\compset} \distrep[1]$
follows by $\reldistrep[1] \pleq^{\compset} \setrep[1]$ and
$\setrep[1] \enp{b} \pleq^{\compset} \distrep[1]$ from above.

* Reduction $\gridrep[1] \pleq^{\compset} \setrep[1]$:
Any $\gridrep[1]$-name $\phi$ induces a $\setrep[1]$-name $\phi'$ of the
same set by $\phi'(q,0^n) \dfeq \max_p \st[0]{ \phi(p,0^{n+1})}{
p \in \ID_{n+1} \cap [q-2^{-n},q+2^{-n}]}$.
Since $|\ID_{n+1} \cap [q-2^{-n},q+2^{-n}]| \leq 5$, constantly
many queries to $\phi$ suffice to devise $\phi'$.

* Reduction $\setrep[1] \pleq^{\regset} \wmemrep[1]$:
Every $\setrep[1]$-name $\phi$ constitutes a $\wmemrep[1]$-name $\phi'$
of the same set through $\phi'(q,0^n) \dfeq \phi(q,0^{n+1})$.

* Reduction $\wmemrep[1] \enp{ar} \pleq^{\regset} \setrep[1]$:
Given a $\wmemrep[1] \enp{ar}$-name $\enc{\phi,a,0^r}$ of
$S \in \CR[1]$, do a binary search between $a$ and $q$ for a point
$p \in \ID_m$, $m \dfeq \max\{n,\abs{r}\}+1$, which minimizes $\abs{q-p}$
over all such points satisfying $\phi(p,0^m)$.
Then $\phi'$ with $\phi'(q,0^n) \dfeq 1$ if
$\abs{q-p} \leq 3 \cdot 2^{-(n+1)}$, and defined as $0$ otherwise,
consitutes a $\setrep[1]$-name of $S$.
Note that convexity is cruicial in order to perform a binary search given
only a $\wmemrep$-name.

§.§.§ Arbitrary yet fixed dimension.

Some of the formerly explained relations change onward from dimension $d = 2$.
As a first example we note a result due to Braverman.

Let $d \geq 2$.
Then $\PTime = \NPTime$ holds true iff
$S$ is polynomial-time $\wrtn{\setrep[d]}{\normdot[2]}$-computable
implies that
$S$ is polynomial-time $\wrtn{\distrep[d]}{\normdot[2]}$-computable
for all $S \in \compset[d]$.

In short:
Finding the distance from a point to a set only from local information
(that is, a $\setrep$-name) about the latter is as hard as solving
$\NPTime$-problems in polynomial time.
Thus, $\distrep[d]$ is richer (, it in a sense provides more
information about closed non-empty sets) than any of the other representations
(, the others are poorer).

We note two implications, following immediately from the proof of

* The statement also holds true over $\KR[d]$.
In fact, it	even uniformizes by an adversary argument as drafted in
<ref>; , $\wrtn{\setrep[d]}{\normdot[2]}
\enp{b} \not\pleq^{\KR} \wrtn{\distrep[d]}{\normdot[2]}$
for $d \geq 2$.

* <Ref> is stated with respect to $\normdot[2]$,
but it easily generalizes to arbitrary well-behaved norms $\normdot$
by properly adapting the adversary set's shape; , from
$\normdot[2]$-balls to $\normdot$-balls.

These two statements also apply to $\gridrep$ due to the following observation.

§.§.§ Representation $\setrep$ with outer radii.

$\gridrep[d]$ can be reformulated as $\setrep[d] \enp{b}$
with necessary outer radius parameter $b$ as
every $\setrep[d] \enp{b}$-name $\enc{\phi,0^b}$ constitutes a
$\gridrep[d]$-name $\phi'$ through $\phi'(\eword) \dfeq 0^b$ and
$\phi'(q,0^n) \dfeq \phi(q,0^{n+1})$ for $q \in \ID^d, n \in \IZ$.
The reverse direction requires a little bit more care:
A point $q$ which does not belong to $B_n$ might still be arbitrarily close
to the represented set, hence $\setrep[d]$-name would have to give $1$
when queried with $\enc{q,0^n}$.

However, any $\gridrep[d]$-name does provide enough information if
only queried on a finite set of points close to $q$.

$\wrtn{\setrep[d]}{\normdot} \enp{b} \pequiv^{\compset}
\wrtn{\gridrep[d]}{\normdot}$ holds in any dimension $d \in \IN$.

By the above argumentation is just remains to prove the reduction
$\gridrep[d] \pleq^{\compset} \setrep[d] \enp{b}$.

Let $q \in \ID^d$ and $n \in \IZ$, and be $\phi$ a $\gridrep[d]$-name of
$S \in \compset[d]$.
Firstly, an outer radius parameter according to $\ens{b}$ can be obtained
through $\phi(\eword)$.
It thus remains to construct a $\setrep[d]$-name $\phi'$ from queries to
We claim that $\phi'(q,0^n) \dfeq \max_{p \in P} \phi(p,0^{n+2})$ with
$P \dfeq \cball(q,3 \cdot 2^{-(n+1)}) \cap \ID^d_{n+2}$ is such a name.
The correctess follows by checking the two cases from definition of $\setrep$.
If $\ball(q,2^{-n}) \cap S \neq \emptyset$, then by <ref> there
must exist a $p \in P$ with $\phi(p,0^{n+2}) = 1$, which leads to
$\phi'(q,0^n) = 1$.
Now consider the second case: $\cball(q,2^{-n+1}) \cap S = \emptyset$.
We prove it by contradition.
To this end, assume $\phi'(q,0^n) = 1$.
Then there is a $p \in P$ which satisfies <ref>, ,
there exists an $x \in S$ such that $x \in \cball(p,2^{-(n+2)})$ which in
turn produces a contradiction because of
$\cball(p,2^{-(n+2)}) \subset \cball(q,2^{-n+1})$.

§.§.§ Local information and relative distance.

On compact sets and enriched with outer radius parameter $b \in \IZ$,
representation $\reldistrep[d]$ is polynomial-time equivalent to $\setrep[d]$.

Recall that by <ref> we assume all representations to be
Without it, only $\sisetrep$

would have been fully polynomial-time equivalent to $\reldistrep$,
while $\setrep$ would have been only parameterized polynomial-time equivalent.]

$\wrtn{\setrep[d]}{\ndot} \enp{b} \pequiv^{\compset}
\wrtn{\reldistrep[d]}{\ndot} \enp{b}$
holds in any dimension $d \in \IN$.

We prove the polynomial-time equivalence of $\reldistrep[d] \enp{b}$ and
$\setrep[d] \enp{b}$ for $\normdot \dfeq \normdot[\infty]$.
The full statement then is a direct application of

Direction $\reldistrep[d] \enp{b} \pleq^{\compset} \setrep[d] \enp{b}$:
Let $n \in \IZ$ and $q \in \ID^d$.
If $\enc{\phi,0^b}$ is a $\reldistrep[d]|^{\compset} \enp{b}$-name of some
$S \in \compset[d]$, then

\[
\phi'\big( q, 0^n \big) \dfeq \begin{cases}
1, & \text{if } \phi(q,0^{n+4}) \leq 5/4 \cdot 2^{-n} + 2^{-(n+4)} \\
0, & \text{if } \phi(q,0^{n+4}) \geq 3/4 \cdot 2^{-n} + 2^{-(n+4)}
\end{cases}
\]

yields $\enc{\phi',0^b}$ to be a $\setrep[d] \enp{b}$-name of $S$.

Reducing $\setrep[d]|^{\compset} \enp{b}$ to
$\reldistrep[d]|^{\compset} \enp{b}$.
Highlighted in black are points $p$ with $\phi(p,0^{n+5-i'}) = 1$.

Direction $\setrep[d] \enp{b} \pleq \reldistrep[d] \enp{b}$:
Let $b' \dfeq \max\{1,b\}$ and $c' \dfeq \lb{\max\{2,\norm{q}\}}$.
We start by determining an initial approximation to $\dist{S}(q)$.
To this end, start with $k \dfeq 0$ and search for the
smallest value $k \leq n+b'+c'+1$ with $\phi(q,0^{n+1-k}) = 1$.
Denote this particular integer by $k'$.
Note that such a $k'$ does exist because of
$S \subseteq \clb(0){0}{2^b+\norm{q}} \subseteq \clb(0){0}{2^{b'+c'}}$.
This $k'$ then yields the bound $\dist{S}(q) \in [2^{-(n+2)+k'},2^{-n+k'}]$.

Now that we have a bound on $\dist{S}(q)$ we can decompose
$\cball(q,2^{-n+k'},2^{-(n+2)+k'})$ into a constant number of regions to
search in for a good approximation to $\dist{S}(q)$.
More precisely, let
$p' \in \ID^d_{n+5-k'} \cap \cball(q,2^{-n+k'},2^{-(n+2)+k'})$ be a dyadic
point with $\phi(p',0^{n+5-k'}) = 1$ which minimizes $\norm{q-p'}$ over
all points from the above hollow set (this argument is also depicted in
This leads to $\abs{\dist{S}(q) - \norm{q-p'}} \leq 2^{-(n+4)+k'}$.

Moreover, $\phi'(q,0^n) \dfeq \norm{q-p'}$ satisfies <ref>.
The first half, the lower bound on $\phi'(q,0^n)$ in
eqn:def-reldistrep, follows by validating that the above bound
on $\norm{q-p'}$ implies $\dist{S}(q) - 2^{-(n+4)-k'} \leq \norm{q-p'}$.
Comparing this bound with $3/4 \cdot \dist{S}(q) - 2^{-n}$ from
eqn:def-reldistrep shows that
$\dist{S}(q) \geq 2^{-(n+2)+k'} - 2^{-n+2}$ has to hold in order to prove
the lower bound from eqn:def-reldistrep to be true which it does (cf. the initial approximation we got on $\dist{S}(q)$).
The upper bound follows analogously.
Hence, $\enc{\phi',0^b}$ is a $\reldistrep[d] \enp{b}$-name of $S$.

§.§.§ Comparing local information.

The situation regarding representation $\wmemrep$ is more diverse:
Although $\wmemrep$ is computably equivalent to $\setrep$
over $\CR$-sets (<ref>),
<ref> already showed that additional local
information (an inner point $a$ and an inner radius $2^{-r}$) is necessary
to reduce a $\wmemrep[1]$-name to a $\setrep[1]$-name.
The reduction itself was no more than a binary search, but the applicability
was tied to dimension $1$ and therefore does not extend to dimension
$d = 2$ onward.
Nontheless, $\wmemrep[d]$ can be shown to be polynomial-time
reducible to $\setrep[d]$ and even to $\distrep$! in dimension
$d \geq 2$ given enough additional information, although by a very
different argument.
We start by sketching the positive result about $\wmemrep$'s relation to
$\distrep$ (extending upon <cit.>), and then show that none
of the enrichments could have been directly computed (in polynomial-time)
from a $\wmemrep$-name alone.

$\wmemrep[d] \enp{ar} \enp{b} \pleq^{\bcb} \distrep[d]$ in any dimension $d$.

This result follows by applying arguments from Convex Optimization:
an adaption of the Ellipsoid Method plus a polarity argument.

The Ellipsoid Method allows to first reduce $\wmemrep[d] \enp{ar} \enp{b}$
to an intermediate representation $\wopt[d]$,

called weak optimization representation

A $\phi \in \Baire$ is a $\wopt[d]$-name of $S \in \KR[d]$, if for every
directional (or: cost-) vector $c \in \ID^d$ and precision $n \in \IZ$,
it satisfies

* $\phi(c,0^n) = \eword$ if $\cball(S,-2^{-n})$ is empty; and

* $\phi(c,0^n) = p$ if $p \in \cball(S,2^{-n}) \cap \ID^d$ such that
$\trsp{c} x \leq \trsp{c} p + 2^{-n}$ holds true for all
$x \in \cball(S,-2^{-n})$.

In the second case we also say that $p$ is an almost optimal point
the cost vector $c$ (cf. <ref>).
This case can moreover be reformulated by means of halfspaces
and hyperplanes:
Let $c$ be some real-valued vector and $\alpha \in \IR$.
Then $H^{\leq \alpha}_{c} \dfeq \st{x \in \IR^d}{\trsp{c} x \leq \alpha}$ and,
analogously, $H^{\geq \alpha}_{c}$ are halfspaces, and their intersection
constitutes the hyperplane
$H^{=\alpha}_c \dfeq H^{\leq \alpha}_c \cap H^{\geq \alpha}$.
The aforementioned second case now reads as
$\bigcup_{x \in \cball(x,2^{-n})} H^{\leq \trsp{c} x}_c \subseteq
H^{\leq \trsp{c} p + 2^{-n}}_c$ for $p$ as above.

Weak optimization:
Cost vector $c$, and a set $S \in \KR[2]$ along with an optimal
solution $p_\ast$ and the set of almost optimal solutions.

Like for $\wmemrep$, representation $\wopt$ only makes sense for
regular sets since the first condition would otherwise always hold true,
, for singletons.
The additional restriction to bounded sets moreover is necessary for the
existence of a point $p$ almost optimizing over $S$ in direction of $c$.
To get the “usual” notion of optimization in direction of $c$, first
approximate the normalized vector to $c$ (, compute
$c \cdot \norm[2]{c}^{-1}$ up to the desired precision) and then apply the

Further note that we tied representation $\wopt$ to the Euclidean norm:
The second condition in the definition of $\wopt$ is stated by means of the
the scalar product $\enc{\cdot,\cdot}$ induced by $\ndot[2]$ (,
$\trsp{x} y = \enc{x,y} = 1/4 (\norm[2]{x+y}^2 - \norm[2]{x-y}^2)$).
This does not lead to the most generic definition of $\wopt$, however, it is
a sensible choice because $\ndot[2]$ is the only norm on $\IR^d$
amongst the $p$-norms
$\norm[p]{(x_1,\dots,x_d)} \dfeq \big( \sum_{i=1}^d \abs{x_i}^p \big)^{1/p}$
(for $1 \leq p \leq \infty$)

that induces a scalar product.
We therefore only write $\wopt[d]$, but obviously mean

Using $\wopt$ and the following <ref>, we translate an
$\wmemrep$-name of a set $S$ to a $\distrep$-name of its polar set
$\polar{S}$ (a related but in most instances not the same set), and then use
this as an intermediate step to prove the above s:convex-opt.

$\wmemrep[d] \enp{ar} \enp{b} \pleq^{\bcb} \wopt[d]$.

Define $\polar{} \colon \closedset[d] \to \closedset[d]$ through
$S \mapsto \polar{S} \dfeq
\st[0]{y \in \IR^d}{\xall{x}{S} \trsp{y} x \leq 1}$,
and call $\polar{S}$ the polar of $S$
(a well-known concept in convex geometry and optimization;
cf. <cit.>, <cit.>).
Further, call $S$ centered if $0 \in \inner{S}$.

* For all $S \in \clset[d]$ and $r,b \in \IZ$,
$\cball(0,2^{-r}) \subseteq S$ implies
$\polar{S} \subseteq \cball(0,2^{r})$
and $S \subseteq \cball(0,2^{b})$ implies
$\cball(0,2^{-b}) \subseteq \polar{S}$.

* Let $S \in \KCR[d]$ be centered.
Then $\polar{S}$ is also contained in $\KCR[d]$, centered,
and $S = \dpolar{S}$.

* Let $\mathcal{Z} \dfeq
\st[0]{S \in \KCR[d]}{S \text{ centered}\,}$.
Further define an enrichment (“inner radius of centered sets”)
$\ens{r_0} \dffn S \mmapsto
\st[0]{ \uintrep(r) }{ \cball(0,2^{-r}) \subseteq S }$.

Then $\polar{}|_{\mathcal{Z}}$ is
\wmemrep[d] \enp{r_0} \enp{b}, \distrep[d] \enp{r_0} \enp{b}
\big)$-computable in polynomial time.

Let $\enc[1]{\phi,a,0^r,0^b}$ be a $\wmemrep[d] \enp{ar} \enp{b}$-name of
$S \in \mathcal{Z}$.
Then $\phi'(q,0^n) \dfeq \phi(q-a,0^n)$ gives a
$\wmemrep[d] \enp{r_0} \enp{b}$-name $\enc[1]{\phi',0^{r},0^b}$ of
$S' \dfeq \st{x-a}{x \in S}$.
Since $S'$ is centered and therefore contains $0$ as an inner point,
<ref>(3) can be applied to get a
$\distrep[d] \enp{r_0} \enp{b}$-name $\enc[1]{\phi'',0^{r''},0^{b''}}$ of
$\polar{S'}$ out of $\phi'$ with $r'' \dfeq b$ and $b'' \dfeq r$.
Use the reduction $\distrep[d] \pleq \wmemrep[d]$ and apply
<ref>(3) once again to get a $\distrep[d]$-name $\phi'''$
of $\dpolar{S'} = S'$ (by <ref>(2)) out of $\phi''$.
The final translation $S' \mapsto \st{x+a}{x \in S'}$ through
$\psi(q,0^n) \dfeq \phi'''(q+a,0^n)$ yields a $\distrep[d]$-name $\psi$ of $S$.

Illustrating the definition of $\polar{S}$

Optimization in direction of $\hat{q}$:
Pick an arbitrary point $p \in P(\hat{q})$
the set of optimal points $\hat{q}$ and project it onto $\hat{q}$.
The resulting point $\pi(p,q)$ then allows to recover
the distance of $q$ to $\polar{S}$ from

Construction of and argumentation using polar sets.

The key ingredient in the proof of <ref> is to take the ratio
$2^{-r}/2^b$ into account.
If done correctly, this then ensures that we get a sufficiently good
approximation of a bounding hyperplane $H^{\leq 1}_{p'}$ from which the
distance and hence a $\distrep$-name can be easily calculated.
We wrap the necessary technical details in the following statement.

Let $S \in \KCR[d]$ be centered.
Further let $r \in \IZ$ and $b \in \IZ$ be inner and outer radius parameter,

* Let $\phi$ be a $\wopt[d]$-name of $S$.
Then $p \dfeq \phi(q,0^m)$ satisfies

\[
\some{p_\ast}{S}{
p_\ast \in \cball(p,2^{-n})
\text{ and }
\xall{x}{S} \trsp{q}x \leq \trsp{q}p_\ast
\]

if $m \geq n + \abs{b} + \abs{r} + 1$.

* Denote by $\pi \dffn (p,q) \mapsto
\trsp{p} q \cdot 1/(\trsp{q} q) \cdot q$ the projection of
$p \in \IR^d$ onto $q \in \IR^d$.
If $\pi(p,q)$ with $p \in \boundary{S}$ is approximated by
$p' \in \ID^d$ with precision $m \geq n + \abs{b} + \abs{r} + 1$, then

\[
\dH\big(
\cball(0,2^b+2^r) \cap H^{=1}_{p'},\,
\cball(0,2^b+2^r) \cap H^{=1}_{\pi(p,q)}
\big) \leq 2^{-n}
\eqnsp .
\]

Stated differently, vectors $\pi(p,q)$ and $p'$ describe approximately the
same hyperplane (with respect to bounds $b$ and $r$).

Note that the polar of a closed set is closed, too, as per definition
it is the intersection of closed halfspaces, ,
$\polar{S} = \bigcap_{x \in S} H^{\leq 1}_x$ with halfspaces
$H^{\leq 1}_x \dfeq \st{y \in \IR^d}{\trsp{x} y \leq 1}$.
Statement (2) now is a special case of the Bipolar Theorem
(cf. <cit.>), while statement (1) follows by examining the
proof of the aforementioned theorem (cf. <cit.>).

Concerning (3):
Let $\enc{\phi,0^r,0^b}$ be a
$\wmemrep[d]|^{\mathcal{Z}} \enp{r_0} \enp{b}$-name of $S \in \mathcal{Z}$,
$q \in \ID^d$ and $n \in \IN$.
Apply <ref> to the above name to get a
$\wopt[d]|^{\mathcal{Z}} \enp{r_0} \enp{b}$-name $\enc{\phi',0^r,0^b}$
of $S$.

Notice beforehand that <ref> allows us to describe all of
the following steps in terms of exact computations while they actually
have to be carried out approximately.
To get the approximative (and hence correct) version, use the aforementioned
results and the closure of polynomial-time function computation under

As already mentioned in <ref>, optimization in a certain
direction in the usual sense is obtained from a $\wopt$-name by
first normalizing the respective cost vector; ,
$q' \dfeq q/\norm{q}$ in this setting.
Now take the $\wopt$-name $\phi'$ and apply it to $q'$ to obtain an
optimal point $p \dfeq \phi'(q',0^m)$.
The point $p$ itself usually does not describe the distance between $q$ and
$\polar{S}$ appropriately as depicted in <ref>, but its
projection onto $q'$ encodes precisely this information.
To this end, let $p' \dfeq \pi(p,q')$ (use <ref>(2) to
get a good approximations) and observe that the distance of
$q$ from $\polar{S}$ can be obtained from the distance of $q$ to the
hyperplane $\st[0]{y \in \IR^d}{\trsp{y} p' = 1} = H^{=1}_{p'}$ under the
premise that $\trsp{q} p' \geq 1$.
More concretely, a valid $\distrep[d]|^{\mathcal{Z}}$-name $\varphi$ of
$\polar{S}$ can be defined as follows:

\begin{align*}
\label{eqn:wmem-wopt-proj}
\varphi(q,0^n) \dfeq 0
\text{ if }
\trsp{q} p' \leq 1 + 3 \cdot 2^{-(n+1)} \cdot \norm{p'}
\eqnsp ; \quad
\varphi(q,0^n)
\dfeq (\trsp{q} p' - 1) \cdot \norm{p'}^{-1}
\text{ otherwise}
\eqnsp .
\end{align*}

Considering (1):
First note that $\dH\big( S, \cball(S,-2^{-m}) \big) \leq 2^{-(n+1)}$
if $m \geq n + \abs{b} + \abs{r} + 1$ which follows by a geometric argument:
Observe that $S$ does contain a filled right-angled triangle $T$ with
adjacent side of length $\leq 2^b$ and opposite side of length $\geq 2^{-r}$.
The ratio $2^{-r}/2^b$ bounds how “steep” this triangle can be.
Stated differently, for all $x \in \boundary{T}$ there exists a
$y \in \clb{T}{-2^{-m}}$ with $\norm{x-y} \leq 2^{-(n+1)}$ for $m$ as above;
which implies the above statement about the Hausdorff-distance of
$\clb{S}{-2^{-m}}$ to $S$.

The definition of $\wopt$ now implies that each almost optimal
$p \in \cball(S,2^{-m})$ fulfills $\trsp{q}x \leq \trsp{q}p + 2^{-m}$
for all $x \in \cball(S,-2^{-m})$.
Combine this bound with the first argument over the Hausdorff distance to
obtain the claimed result, namely that there exists an optimal point
$p_\ast \in S \cap \cball(p,\delta)$ with
$\delta \dfeq (2^{-(n+1)} + 2 \cdot 2^{-m})/2 < 2^{-(n+1)}$ optimization
direction $q$.

Considering (2):
First note that $p \in \boundary{S}$ implies $\norm{p} \geq 2^{-r}$, and also
$\norm{p} \leq 2^{b}$ due to $S \subseteq \cball(0,2^b)$.
Without loss of generality, let $\pi(p,q) \dfeqrev (\lambda,0,\dots,0)$ and
$p' \dfeq (\lambda \pm 2^{-m},0,\dots,0)$ (the latter being a boundary case of
$p' \in \cball(\pi(p,q),2^{-m})$) with $2^{-r} \leq \lambda \leq 2^b$
(as noted before).
In this particular case $\pi(p,q)$ and $p'$ are codirectional which simplifies
the following argument.
Note that $\trsp{\pi(p,q)} x = 1$ if $x_1 = 1/\lambda$,
and $\trsp{p'}x' = 1$ if $x'_1 = 1/(\lambda+2^{-m})$.
Then the codirectionality of $\pi(p,q)$ and $p'$ imply that
$H^{=1}_{\pi(p,q)}$ and $H^{=1}_{p'}$ are parallel, and they are of Hausdorff
distance $\abs{1/\lambda - 1/(\lambda+2^{-m})}$.
By $2^{-r} \leq \lambda \leq 2^b$.
Therefore, $\abs{1/\lambda - 1/(\lambda+2^{-m})} \leq 2^{-n}$ by
$m \geq n + \abs{r} + \abs{b} + 1$, and thus implies

\[
\dH\big(
\cball(0,2^{b}+2^{r}) \cap H^{=1}_{p'},\,
\cball(0,2^{b}+2^{r}) \cap H^{=1}_{\pi(p,q)}
\big) \leq 2^{-n}
\eqnsp .
\vspace*{-2em}
\]

Both the enrichments ($a$, $r$ and $b$) as well as the restriction to bounded
convex bodies $\bcb$ were necessary to make <ref> work, as
we summarize in the following statement.

For all $d \in \IN$ we get the following negative results:

0. The multi-valued operation
$\mathsf{Bound} \colon \KR[d] \mto \IZ$,
$\KR[d] \ni S \mmapsto \st{b \in \IZ}{S \subseteq \cball(0,2^b)}$
is $(\wmemrep[d] \enp{ar}, \unaryrep)$-discontinuous.
The analogous fact holds for $\setrep[d]$
(cf. <cit.>).

* Convexity is a crucial ingredient to make <ref>
work: $\wmemrep[d] \enp{ar} \enp{b} \not\preceq^{\KR} \distrep[d]$.

Addendum to the previous point:
Convexity does only help in the presence of all of the above
enrichments; , there is no machine operating on $\bcb[d]$
that provided with $\wmemrep[d] \enp\chi_1 \enp\chi_2$ computes
$\chi_3$ in polynomial time for any permutation
$\{ \chi_1,\chi_2,\chi_3 \}$ of $\{ \ens{a},\ens{r},\ens{b} \}$.

* Over $\bcb[d]$, advice parameters $\ens{a}$, $\ens{r}$ and $\ens{b}$
are uniformly computable from $\setrep[d]$.
The same statement fails, however, for computability in
polynomial time.

0. Let $M^?$ be a hypothetical OTM to compute $\mathsf{Bound}$.
Further, let $\enc{\phi,a,0^r}$ be a $\wmemrep[d]|^{\KR} \enp{ar}$-name
for $S \in \KR[d]$.
Machine $M^?$ terminates (in finite time) and produces a potential bound
During its computation it can only have made finitely many queries to
$\phi$ and thus has checked only points in, say,
$\cball_{\normdot}(0, 2^{b'})$ for some $b' \in \IZ$.
Therefore, $M^?$ would have produced the same potential bound $b \leq b'$
if $S$ were replaced with the set
$S' \dfeq S \cup \cball_{\normdot}(p, 1)$ for some point $p$ satisfying
$\cball_{\normdot}(0, 2^{b'}) \cap \cball_{\normdot}(p,1) = \emptyset$.

* We prove the stronger statement
$\wmemrep[d] \enp{ar} \enp{b} \not\preceq^{\KR} \setrep[d]$.

Let $S \dfeq \cball_{\normdot}(0, 2^b, 2^b-2^{-3})$, and be
$\phi \dfeq \enc{\phi',a,0^r,0^b}$ with $\phi'(q',n') \dfeq \chi_{S}(q')$
a concrete $\wmemrep[d]|^{\KR} \enp{ar} \enp{b}$-name of $S$.
Further let $M^?$ be a hypothetical OTM translating any $\phi$ into a
The discrete inputs (tailor-made for the adversary argument) are
$q \dfeq (0,\dots,0)$ and $n \dfeq 3$.
On this input, $M^?$ does asks queries of precision at most $m \geq \abs{r}$.
Therefore, it states “0” as the correct answer a
$\setrep[d]$-name would have given on $\enc{q,0^n}$
because of $\cball(0, 2^{-3+1}) \cap S = \emptyset$.
$M^?$ surely produces the right answer for $S$, but it also does so on the
slightly modified (adversary) set $S' \dfeq S \cup \cball(0, 2^{-(m+2)})$
for all $\wmemrep[d]|^{\KR}$-names $\phi''$ for $S'$ with
$\xall{p}{\ID^d} \xall{k}{\IN,\, k \leq m} \phi'(p,0^k)=\phi''(p,0^k)$;
thus misleading $M^?$ to produce the wrong answer ($0$ instead of $1$).

* Parameter $b$ can not be computed in polynomial time from $r$, $a$
(and $n$) because the outer radius of a set $S$ is simply not bounded in
this (local) information about $S$.

Finding an inner point $a$ from $b$ and $r$ requires to query a
$\wmemrep[d]|^{\KCR}$-name $\phi$ in roughly $2^{d \cdot \max\{0,b+r\}}$
many points.
To see why, consider the collection of adversary sets
$\st[0]{S_{p} \dfeq \cball(p,2^{-r})}{p \in \cball(0,2^b) \cap \ID^d_{r+1}}$
and observe that $S_p$ can only be distinguished from any other $S_{p'}$
if $\phi$ is evaluated in $p$ and $p'$ with precision $r+1$.

An analogous argument shows why an inner radius parameter $r$ can not be
deduced solely from $a$ and $b$.

* Computability of $b$, $a$ and $r$:
Let $\phi$ be a $\wrtn{\setrep[d]}{\normdot}$-name of $S \in \KCR[d]$.
An outer radius parameter $b$ exists since $S$ is bounded, and it is
computable from $\phi$ by exploiting convexity:
Starting at $0$, systematically ask queries $\phi(p,0^1)$ with
$p \in \ID^d_1$ in order to find a value $b \geq 1$ such that
(a) $\xsome{p}{\ID^d_1 \cap \clb(0){0}{2^{b-1}}} \phi(p,0^1) = 1$ and
(b) $\xall{p}{\ID^d_1 \cap \clb(0){0}{2^b}} \phi(p,0^1) = 0$.
It then follows $S \cap \clb(0){0}{2^{b-1}} \neq \emptyset$,
and $S \subset \clb(0){0}{2^b}$ is implied by using the convexity of $S$.

From $b$ one can find a point $a$ and also an inner radius parameter $r$
by gradually increasing the precision:
Starting with $r' \dfeq -b+3$, increase $r'$ until a point
$p' \in \ID^d_{r'}$ in $\clb(0){0}{2^b}$ is found such that all
$p \in \ID^d_{r'} \cap \clb(0){p'}{2^{-r'+3}}$ satisfy
$\phi(p,0^{r'}) = 1$.
Then $\clb(0){p'}{2^{-r'}} \subseteq S$ follows by convexity of $S$.
Now choose $a \dfeq p'$ and $r \dfeq r'$.

Non-polynomial-time computability:
Any (deterministic) computation of $b$ and $r$ must necessarily be
unbounded in $n$ (and, obviously, $|\phi|$), simply because the
values of both $b$ and $r$ are usually unbounded in $n$.
The same is true for an inner point $a$ since it depends on (the
unknown) inner radius parameter $r$; take $S = \cball(a,2^{-r})$,
$a \in \ID^d_r \setminus \ID^d_{r-1}$ as an example.

<Ref>(2) covers, in fact,
several constellations of enrichments of $\wmemrep$ because it implies,
roughly said, “if we can not deduce $\chi_3$ from $\wmemrep[d]$ and
two-thirds of other information ($\chi_1$ and $\chi_2$), then particularly
neither none nor one-third of it would help, too”.

§ GEOMETRIC OPERATIONS ON SETS

By definition, both the computability and complexity of an operator is
inextricably linked to the choice of representations of elements it is based
on; examples can be found in <cit.>, <cit.>,
<cit.>, <cit.> (for computability), and
<cit.> (for complexity). While the computability is pretty well-studied,
the complexity has been left
behind as, again, a result of the missing generic framework to formulate
explicit complexity bounds in.
In this section, we do our small part to shine a light on the complexity of
$\dsoch$ (finding some point in a set), set operators $\dsocup$,
$\dsocap$ and $\mathsf{Projection}$, and basic function operators $\dsoinv$
(local inverse of a function) and $\dsoimg$.

§.§ $\dsoch$: Finding a point in a set

We analyze the complexity to compute some (multi-valued) member of a
set $S$, given only a name of $S$; , the complexity of the in general
uncomputable (cf. <cit.>) operator
$\dsoch \colon \closedset \mto \bigcup_{d\in\IN} \IR^d$,
$\closedset \ni S \mmapsto S$.
It is an interesting operator because, intuitively, at least this operator
should be (parameterized) polynomial-time computable for reasonable
representations of sets; like the operator
$\mathsf{Evaluation} \colon (f,x) \mapsto f(x)$ is in the realm of continuous
functions <cit.>.

The following statement indeed proves parameterized complexity results for
In particular, $\setrep$ enriched with $\ens{b}$ suffices, while even
more information is necessary for $\wmemrep$.

* On compact sets, $\dsoch|_{\compset}$ is
fully polynomial-time $(\setrep[d] \enp{b}, \realrep[d])$-computable.

$\dsoch|_{\KR}$ is $(\wmemrep[d] \enp{r} \enp{b},\realrep[d])$-computable
in time polynomial exponential in $\abs{b} + \abs{r}$.
This bound also is sharp (, no fully polynomial-time bound can be

* Let $S \in \compset[d]$, $\enc{\phi,0^b}$ be a $\setrep[d] \enp{b}$-name
of $S$ with $b \geq 0$, and $n \in \IZ$.
A point $q \in \ID^d$ with $\phi(q,0^n) = 1$ can then be found by the
following iterative procedure.
First, let $p_{0} \dfeq 0$.
Now assume that $p_{i-1}$ for $1 \leq i \leq n+b+2$ is already given.
Then deterministically pick one point $p_i$ out of
$\cball(p_{i-1},2^{b-(i-1)}) \cap \ID^d_{i-b}$ with
$\phi(p_i,0^{i-b}) = 1$.
Then $p_{n+b+2}$ is guaranteed to be $2^{-n}$-close to $S$.

* Let $\enc{\phi,0^r,0^b}$ be an $\wmemrep[d]|^{\KR} \enp{r} \enp{b}$-name
of $S \in \KR[d]$.

Upper bound:
Perform an exhaustive search on $\ID^d_{r+1}(2^b)$. This way
$\phi(p,0^{r+1}) = 1$ is guaranteed by $2^{-r}$ being an inner
radius of $S$ for some point $p \in \ID^d_{r+1+n}(2^b)$. Moreover, such
a point will be found and is close-enough (in the sense of
representation $\realrep[d]$) to $S$.

Consider the class of sets
$\mathcal{B} \dfeq \st{ \cball(a,2^{-r}) }{
a \in \ID^d_{r+n'}(2^b), n' \in \IZ } \subset \KR[d]$.
The sharpness then is a consequence of <ref>(2),
$\wmemrep[d] \enp{r} \enp{b} \not\pleq^{\mathcal{B}} \setrep[d]$:
Exponentially many points $p \in \ID^d$ have to be considered in order to
tell any of the above sets apart.

§.§ Binary union

<cit.> proved $\dsocup$ to be linear-time computable over
$\gridrep$ their notion of complexity:
Given two $\gridrep[d] \pequiv^{\compset} \setrep[d] \enp{b}$-names
$\phi_1$ and $\phi_2$, taking the maximum over the outer radii parameter as
well as the maximum over the answers at any point,
$\phi(q,0^n) = \max_i \phi_i(q,0^n)$, constitutes a name of the union.
Linear-time algorithms for $\setrep[d]$ and $\distrep[d]$ follow analogously.

However, the same method applied to $\wmemrep[d]$ over regular sets does
not yield a valid $\wmemrep[d]$-name of the union.
As it turns out, $\dsocup$ is even uncomputable over $\wmemrep[d]$.
Convexity, again, proves to be the key to render $\dsocup$ computable,
even in polynomial time.

* $\dsocup|_{\KR \times \KR}$ is
$\big((\wmemrep[d] \enp{r} \enp{b}) \times (\wmemrep[d] \enp{r} \enp{b}),
\wmemrep[d]\big)$-discontinuous.

* On $\cb[r]$, however, $\dsocup|_{\cb \times \cb}$
becomes polynomial-time
$(\wmemrep[d] \times \wmemrep[d], \wmemrep[d])$-computable.

$\dsocup|_{\KR \times \KR}$ is $\wmemrep[d]$-discontinuous:
The adversary set on the left is indistinguishable from the right one
provided the “stripes” are just small enough to not contain a
ball of radius $2^{-m}$.

Alternately cut small pieces of “size”
$2^{-(m+2)}$ off of two copies of the unit interval (in general:
unit hypercube) to obtain an empty intersection around point $q$.

Adversary arguments, proving the discontinuity of
(a) $\dsocup$ over $\wmemrep$ and (b) $\dsocap$ over $\setrep$.

* The basic adversary construction of sets $S_i$ and $\tilde{S}_i$ is
depicted in <ref>.
First choose $S_i$ such that $\cball(q,2^{-n+1})$ has an empty intersection
with $S_1 \cup S_2$ (, as a simple “stripe” as depicted).
Further construct $\tilde{S}_i$ as follows:

* $r_i$ is an inner radius parameter of $\tilde{S}_i$;

* the “spikes”, being of length $> 2^{-n+2}$, are placed
around $q$ as depicted;

* each “spike” is of height $\leq 2^{-(m+1)}$,

where $m \in \IN$ marks the maximal precision a hypothetical OTM
$M^?$ for $\dsocup$ asks on input $\enc{q,0^n}$.
Now the only (and in this case correct) choice $M^{\enc{\phi_1,\phi_2}}$
started with $\enc{q,0^n}$ has is to assert $0$ since
$\cball(q,2^{-n+1}) \cap (S_1 \cup S_2) = \emptyset$.
Now exchange the names for $S_i$ by names $\tilde{\phi}_i$ for
$\tilde{S}_i$ which coincide with the previous ones on all queries up to
precision $m$.
Then $M^{\enc{\tilde{\phi}_1,\tilde{\phi}_2}}$ sill asserts $0$ in this
case, although now $\ball(q,2^{-n}) \subset \tilde{S}_1 \cup \tilde{S}_2$
proves $1$ to be the only correct choice.

* Let $\phi_i$ be $\wmemrep[d]$-names of $S_i$, $i = 1,2$.
Claim: Then $\phi'$, defined through

\[
\phi'(q,0^n) \dfeq \max_{i = 1,2} \st[1]{ \phi_i(p,0^{n+2}) }{
p \in B \dfeq \cball(q, 3 \cdot 2^{-(n+2)}) \cap \ID^d_{n+2}
\eqnsp ,
\]

constitutes a $\wmemrep[d]$-name of $S' \dfeq S_1 \cup S_2$.

Let $\cball(q,2^{-n}) \cap S' = \emptyset$.
Then $\bigcup_{p \in B} \cball(p,2^{-(n+2)}) \subset S'$ must also has an
empty intersection with $S'$, hence $\phi_i(p,0^{n+2}) = 0$ for all
$p \in B$ and $i \in \{1,2\}$.
Now let $\cball(q,2^{-n}) \subseteq S'$.
We prove the correctness of $\phi'(q,0^n) \dfeq 1$ by contradiction.
To this end, assume $\phi'(q,0^n) = 0$, ,
$\cball(p,2^{-(n+2)}) \not\subseteq S_1, S_2$ would have to hold for all
$p \in B$.
Because of $\cball(p,2^{-(n+2)}) \subset \cball(q,2^{-n}) \subseteq S'$
and the convexity of $S_i$, there must be a $p' \in P$ such that
$\cball(p',2^{-(n+2)})$ is contained entirely either in
$S_1 \cap S_2$, $S_1 \setminus S_2$ or $S_2 \setminus S_1$.
If $\cball(p',2^{-(n+2)})$ were contained in the first (convex) set, then
we would get a contradiction because of
$\cball(p',2^{-(n+2)}) \not\subseteq S_1,S_2$.
If it were contained in (one of the connected regions of)
$S_1 \setminus S_2$, then we would also get a contradiction to the
assumption that $\cball(p',2^{-(n+2)}) \not\subseteq S_1$.
The analogous argument also holds for the third set, thus proving
$\wmemrep[d](\phi') = S'$.

§.§ Binary intersection

$\dsocap$ proves to be discontinuous for $\distrep$ over the class
$\closedset$ of closed sets <cit.> by the usual adversary
Whenever a (hypothetical) algorithm decides upon a certain point $x$ to be a
member of the intersection, we can slightly modify the original sets by
excluding points from a small neighborhood of $x$, rendering $x$ to be far
off the actual intersection and therefore leading any hypothetical OTM to
produce a wrong answer.

Even in case the intersection of two regular sets were regular again,
this discontinuity would not disappear <cit.>.
We show how convexity helps to establish computability, and
how the complexity is bounded in terms of an inner radius of the

\begin{align*}
\mc{D} & \dfeq \st[1]{(S_1,S_2) \in \regset[d] \times \regset[d]}{
S_1 \cap S_2 \in \regset[d]}
\eqnsp ; \\
\mc{E} & \dfeq \st[1]{(S_1,S_2) \in \KCR[d] \times \KCR[d]}{
S_1, S_2 \in \KCR[d]} \subset \mc{D}
\eqnsp ,
\end{align*}

and further define the enrichment $\ens{r'}$ to encode an inner radius
parameter of the intersection of two sets, ,
$\ens{r'} \dffn (S_1,S_2) \in \mc{D} \mmapsto
\st[1]{\uintrep(r')}{\xsome{a}{\IR^d} \cball(a,2^{-r'}) \subseteq S_1 \cap S_2}$.

* $\dsocap|_\mc{D}$ is
$(\reptpl[d] \times \reptpl[d], \reptpl[d])$-discontinuous for
all representations $\reptpl$ from <ref>.

* $\dsocap|_{\mc{E}}$ is
$(\reptpl[d] \times \reptpl[d], \reptpl[d])$-computable for all
representations $\reptpl$ from <ref>.

* $\dsocap|_{\mc{E}}$ is
parameterized polynomial-time
$\big((\reptpl[d] \enp{b}) \times (\reptpl[d] \enp{b}) \enp{r'},
\reptpl[d]\big)$-computable
for $\reptpl[d] \dfeq \setrep[d]$, and
fully polynomial-time computable for
$\reptpl[d] \dfeq \wmemrep[d]$.

Notice the duality in the $\wmemrep[d]$-result for $\dsocap|_\mc{E}$
compared with $\dsocup$:
While for the first a correct answer was easy to produce when the point was
not deep-enough in at least one of the two sets, it was easy to produce a
correct answer for the latter if the point resided deep in both sets.
Further note that this is the direct opposite of what holds for $\setrep$;
an indication that $\setrep$ is dual to $\wmemrep$, just like the union of
sets is the topological dual operation to intersection.

* We only show the $\setrep[d]$-discontinuity of $\dsocap$ (the proof
loosely follows <cit.>);
the remaining statements follow by the same construction.

Let $S_1, S_2 \dfeq [-1,1]^d$ be the sets provided to $\dsocap$
through $\setrep[d]$-names $\phi_1,\phi_2$.
It follows that any $\setrep[d]$-name $\phi'$ of
$S' \dfeq S_1 \cap S_2 = [-1,1]^d$ has to satisfy $\phi'(q,0^n) = 1$
for all $q \in \ID^d \cap [-1,1]^d$ and $n \in \IN$.
Assume that a name for $S'$ is computed by a hypothetical OTM $M^?$
for $\dsocap$, and let $m \in \IN$ be the maximal precision of queries
$M^{\enc{\phi_1,\phi_2}}$ asks when started on input $\enc{q,0^n}$
with $q \dfeq (0,\dots,0)$.
Now exchange $\phi_i$ by a $\setrep[d]$-name $\tilde{\phi}_i$ for
$\tilde{S}_i$ (depicted in <ref>)
which fulfills $\tilde{\phi}_i(p,0^k) = \phi_i(p,0^k)$ for all
$p \in \ID^d$ and $k \leq m$.
Then $M^{\enc{\tilde{\phi}_1,\tilde{\phi}_2}}\enc{q,0^n}
= M^{\enc{\phi_1,\phi_2}}\enc{q,0^n} = 1$
although $\tilde{S}' \dfeq \tilde{S}_1 \cap \tilde{S}_2
= \cball_{\ndot[\infty]}(q,1,1-2^{-n+1})$ and therefore
$\cball(q,2^{-n+1}) \cap \tilde{S}' = \emptyset$ for $n \geq 3$.

* Apply $\reptpl[d] \preceq^{\KCR} \setrep[d] \enp{r} \enp{b}$
(<ref> + <ref>(3))
to the domain-side and $\setrep[d] \preceq^{\KCR} \reptpl[d]$
(<ref>) to the codomain-side, then use statement 3.

* The second part, with $\reptpl[d] \dfeq \wmemrep[d]$, has been
proved in <cit.>.

Intersecting two convex bodies when additional information
about their intersection (an inner ball and an outer radius) is

Let $\enc[1]{\phi_1,\phi_2,0^{b_1},0^{b_2},0^{r'}}$ be a
$( \setrep[d] \enp{b} \times \setrep[d] \enp{b} ) \enp{r'}$-name of
$(S_1,S_2) \in \mc{E}$.
Due to convexity, $S' \dfeq S_1 \cap S_2$ only meets $\clb{q}{2^{-n}}$ if
$S'$ contains a cone whose apex lies in $\ball(q,2^{-n})$.
Therefore, we derive a lower bound $N \in \bigO(n + b_1 + b_2 + r')$ on
the inner radius parameter of $S'$ close to $q$;
, a radius that guarantees the
existence of a ball, say $\clb{p}{2^{-N}}$, which is contained in $S'$ and
also is sufficiently close to $q$; ,
$\clb(0){p}{2^{-N}} \subseteq S' \cap \clb(0){q}{2^{-n+1}}$.
This argument is also depicted in <ref>;
and it yields the following bound on $N$:

\begin{align*}
3/2 \cdot 2^{-n} \cdot \Big(
2 \cdot 2^{-r'} \cdot (2^{\max\{b_1,b_2\}+1} - 2^{-r'} - 2^{-n})^{-1}
\Big)
\geq 2^{-(n + r' + \max\{b_1,b_2\})}
\geq 2^{-N}
\eqnsp .
\end{align*}

Finally, construct $\phi'$ by a local search around $q$:

\begin{align*}
\phi'(q, 0^n) \dfeq \max \st[2]{
\min_{i = 1,2} \phi_i \big( p, 0^N \big)
p \in \cball(q, 3/2 \cdot 2^{-(n+1)}) \cap \ID^d_N
\eqnsp .
\end{align*}

Due to the locality of this search, the number of points to be considered
is exponential in $r$ and $\max\{b_1,b_2\}$, but polynomial in $n$.

§.§ Projection operator

For $d \in \IN$ and $d \geq e$ let $\dsoproj$ be the operator
$\dsoproj_{d,e} \dffn \compset[d] \to \compset[e]$,

\[
S \mapsto \dsoproj_{d,e}(S)
\dfeq \st{x \in \IR^d}{\xsome{y}{\IR^{d-e}} (x,y) \in S}
\eqnsp ,
\]

projecting a $d$-dimensional set $S$ to a subspace of dimension $e$.
Convexity again turns out to be the key to prove polynomial-time bounds.

* Let $d \geq 2$.
The statement “if a set $S \in \compset[d]$ is polynomial-time
$\gridrep[d]$-computable, then operator $\dsoproj_{d,1}(S)$ is
polynomial-time $\gridrep[1]$-computable” is equivalent to
$\PTime = \NPTime$.

* $\dsoproj_{2,1}|_{\KC}$ is polynomial-time
$(\gridrep[2], \gridrep[1])$-computable.

The proof of the second argument can be extended to $\dsoproj_{d,d-1}$ which by composition $\dsoproj_{e+1,e} \circ \cdots \circ \dsoproj_{d,d-1}$
implies the polynomial-time $(\gridrep[d],\gridrep[e])$-computability of
Moreover, the second result carries over to the seemingly poorest
representation $\wmemrep$, but only if restricted to bounded convex
bodies $\KCR$.

Let $d \geq e \in \IN$.

* $\dsoproj|_{\KR}$ is
$(\wmemrep[d] \enp{r} \enp{b}, \wmemrep[e])$-discontinuous
for $d \geq 2$.

* Nonetheless:
$\dsoproj|_{\KCR}$ is $(\wmemrep[d] \enp{b}, \wmemrep[e])$-computable, and
(with proper enrichments) it even becomes
$(\wmemrep[d] \enp{ar} \enp{b}, \wmemrep[e])$-computable in polynomial time.

* Apply the adversary argument we have seen several times before.
The discontinuity then follows by cutting the unit hypercube $[0,1]^d$
up via a “chess-board”-like pattern.

* Use $\wmemrep[d] \enp{ar} \enp{b} \pleq^{\KCR} \setrep[d]$
(<ref>) and
$\setrep[d] \enp{b} \pequiv^{\compset} \gridrep[d]$
<ref>) on the domain side,
$\gridrep[e] \pleq^{\compset} \setrep[e] \pleq^{\KR} \wmemrep[e]$ on
the co-domain side, and then apply the comment on the complexity of
$\dsoproj_{d,e}|_{\KC}$ following <ref>.

§ FUNCTION INVERSION AND IMAGE COMPUTATION

In this section we discus the complexity of function inversion and image
computation; , of $(f,S) \mapsto (f|_{S})^{-1}$ for the former, and
$(f,S) \mapsto f[S]$ for the latter.
One issue we have to deal with is that the coding length of function values
is usually not bounded in terms of the coding length of their respective
function arguments.
To this end, we revise the previous notion of complexity
to measure the running time both in the discrete argument and the
given name.
This more general complexity notion then covers <ref>
and moreover allows us to prove the complexity of the aforementioned operators.

By convenience and supported by the results from <ref>, we
formulate the following definitions and results with respect to
$\normdot \dfeq \normdot[\infty]$.

§.§ Prerequisites

Following <ref> we already discussed the need to add
advice parameters in order to state the complexity of operators solely in
the coding length of their discrete arguments.
As an example we saw $\distrep|^{\compset}$ with
advice parameter $b$. This trick to add advice parameters in order to bound
the oracle answer length, however, does not always work: there is no parameter
bounding the length of $\distrep$-names on discrete arguments unless $\distrep$
is restricted to compact sets. The same applies to representation
$\dyfunrep{d}{e}$ of $\cfn(\IR^d,\IR^{e})$:
Like for closed versus compact sets in $\distrep$-representation,
the values of continuous functions can not be bounded
in terms of the argument's coding length if the image is unbounded.
The following definition of second-order polynomials and
second-order polynomial time (devised and investigated in a sequence
of papers <cit.>) provides a solution by defining a
notion of length in both the discrete argument and the oracle.
A recent attempt to generalize from second-order to higher-order complexity
can be found in <cit.>.

* A total function $\phi \colon \Sast \to \Sast$ is
length-monotone if $\len{\phi(s)} \leq \len{\phi(t)}$ holds true
whenever $\len{s} \leq \len{t}$ for $s,t \in \Sast$. We denote the set
of length-monotone functions by $\Reg$.

* On $\phi \in \Reg$ define a notion of length through
$\len{\phi}(m) \dfeq \len{\phi(0^m)} =
\max_{s \in \Sast.\,\len{s} \leq m} \len{\phi(s)}$.
[Notice the overloading of the length-function $\len{\cdot}$:
Depending on the context, it denotes the length of either words
or length-monotonic functions.
But this overloading “behaves well” in the sense that
every word $s \in \Sast$ can be associated with the constant function
$\phi_s \dffn t \mapsto s$ so that the length of $s$ coincides with
the length of $\phi_s$, , $\len{s} = \len{\phi_s}$.]

* A second-order polynomial $P \colon (\IN \to \IN) \to (\IN \to \IN)$
in arguments $L \colon \IN \to \IN$ and $n \in \IN$ is defined inductively:
Every constant $m \in \IN$ is a second-order polynomial, as well as
variable $n$; assuming $Q$ and $Q'$ are second-order polynomials, then
$Q+Q'$, $Q\cdot Q'$ and $L(Q)$ are, too.

We make a few remarks why the above definitions are useful, and how they
subsume <ref>.

* As by construction, the class of second-order polynomials is
closed under addition, multiplication and composition
(just like its first-order counterpart, $\IN[X]$).

* <ref> already showed how to encode multiple
length-monotone functions $\phi_1,\phi_2$ into one,
$\phi \dfeq \enc{\phi_1,\phi_2}$.
This way, $\len{\phi}(m+1) = \len{\phi_1}(m) + \len{\phi_2}(m) + 1$
for all $m \in \IN$.

Let $\reptpl$ and $\reptpl'$ be second-order representations of sets $X$
and $X'$, respectively, and $\ens{E} \colon X \mto \Sast$ be a multi-valued

* As per <ref>(3), any
$\reptpl \times \reptpl'$-name is of form $\enc{\phi,\phi'}$ for
$\phi,\phi' \in \Reg$, and thus itself in $\Reg$ by the previous

* Similarly, any $\reptpl \enp{E}$-name $\phi = \enc{\phi_1,\phi_2}$
is of length
$\len{\phi}(m+1) = \len{\phi_1}(m) + \len{\ens{E}(\reptpl(\phi_2))} + 1$.

As per the last two points, fully polynomial-time computability implies
computability in second-order polynomial-time.

We are now ready to define representations for functions and lengths of names

Let $X \in \compset[d]$, and $f \colon X \to \IR^{e}$ be a continuous function.

* A function $\modcont \colon \IN \to \IN$ is called modulus
of (uniform) continuity of $f$ if $\norm{x - y} \leq 2^{-\modcont(n)}$
implies $\norm{f(x) - f(y)} \leq 2^{-n}$ for all $x,y \in \dom(f)$ and
precisions $n \in \IN$.[
The concepts and arguments in this section generalize to integer

* A $\tuple{\phi,\varphi} \in \Reg$ is a $\funrep[d,e][X]$-name of $f$ if

* $\phi$ satisfies

\begin{align} \label{eqn:cond-total}
\xall{q}{\ID^d \cap X} \xall{n}{\IN}
\vnorm{\phi(q,0^n) - f(q)} \leq 2^{-n}
\end{align}

* $\varphi$ encodes a modulus of continuity $\modcont$ of $f$, ,
$\varphi \dffn s \in \Sast \to 0^{\modcont(\len{s})}$.

In order to simplify the notation we associate $\varphi$ with $\modcont$
and just write $\enc{\phi,\modcont}$ instead of $\enc{\phi,\varphi}$.

* A function $\modsu \colon \IN \to \IN$ is called modulus of
(uniform) unicity of $f$
(cf. <cit.>;
introduced by Kohlenbach in <cit.>, although
in a more general way than we need it here)
if $\norm{f(x) - f(y)} \leq 2^{-\modsu(n)}$
implies $\norm{x - y} \leq 2^{-n}$ for all $x,y \in \dom(f)$ and
precisions $n \in \IN$.

* A $\enc{\phi,\modcont,\modsu} \in \Reg$ is a
$\invrep[d,e][X]$-name of $f$ if $\modcont$ and $\modsu$ are, respectively,
moduli of continuity and unicity of $f$, and
$\funrep[d,e][X] \big( \enc{\phi,\modcont} \big) = f$.

Representations $\funrep$ and $\invrep$ only cover subclasses of total
functions with a priori known domains;
thus asking about the $(\funrep[d,d][X],\funrep[d,d][Y])$-computability
and -complexity of function inversion would only make sense if they were
restricted to total injective and surjective functions of signature
$X \to Y$ only.
Phrased differently, formulating function inversion over a class $\mathcal{F}$
of functions and $\funrep$ only makes sense in case for all functions
$f \in \mathcal{F}$ the (a priori known) codomain matches $\img(f)$;
thus, the inverses of functions in $\mathcal{F}$ had to be total and
(more importantly) had to share the same domain.
This is simply not true in general.
In general, the inverse $g$ of an injective function $f \dffn X \to Y$ is a
partial function from $Y$ to $X$;
but <ref> does not work in case of partial functions:
Any $\phi \in \Reg$ satisfying <ref> and associated to a
partial function $g \parcol X \to Y$ is only defined for
dyadic points in $\dom(g)$, but $\dom(g)$ does not necessarily contain
any dyadic point.

By relaxing on the first universal quantification in <ref> we
obtain new representations $\parfunrep[d,e]$ and $\parinvrep[d,e][X]$
(, multi-representation; cf. <cit.>) which extend
$\funrep[d,e]$ and $\invrep[d,e]$, respectively, and are tailor-made for
partial functions.
They render any name to be defined on all dyadic inputs (not only
those from $X \cap \ID^d$), but only give good approximations
(in the usual sense) if the input is close to the domain of the respective
function (specializing <cit.>).

Let $f \parcol \IR^d \to \IR^{e}$ be a (possibly partial) function with
compact domain.
A $\enc{\phi,\modcont,\modsu}$ is a $\parinvrep[d,e]$-name of $f$ if
$\modcont$ and $\modsu$ are moduli of $f$ and $\phi$ satisfies

\begin{equation}
\label{eqn:cond-partial}
\begin{aligned}
\xall{q}{\ID^d}
\xall{n}{\IN}
\Big(
&	\dom(f) \cap \cball\big(q, 2^{-\modcont(n+1)}\big) \neq \emptyset\\[-1ex]
&	\implies
\xsome{x}{\dom(f) \cap \cball\big(q, 2^{-\modcont(n+1)}\big)}
\norm{\phi \big(q,0^n\big) - f(x)} \leq 2^{-(n+1)}
\Big).
\end{aligned}
\end{equation}

Similarly define $\parfunrep[d,e]$ as the generalization of $\funrep[d,e]$
to continuous partial functions.

Note that by the above construction, every $\parinvrep[d,e]$-name $\phi$ of
some total function $f$ in particular is a $\invrep[d,e]$-name of $f$,
For each $q \in \dom(f)$ there is an
$x \in \dom(f) \cap \cball(q,2^{-\modcont(n+1)})$ such that
$\norm{f(q) - f(x)} \leq 2^{-(n+1)}$.
Applying eqn:cond-partial then yields

\[
\vnorm{\phi(q,0^{n}) - f(q)}
\leq \vnorm{\phi(q,0^{n}) - f(x)} + \vnorm[0]{f(x) - f(q)}
\leq 2^{-(n+1)} + 2^{-(n+1)}
= 2^{-n}
\eqnsp .
\]

§.§ Function inversion: some upper and lower bounds

The $\dsoinv$ operator takes a function $f$ and a subset
$\clset \ni S \subseteq \dom(f)$, and (under the assumption
on $f$ having a local inverse on $S$) maps $(f,S)$ to the inverse of $f|_S$.
In this section we focus on the parameterized complexity of this

While $\dsoinv$ is polynomial-time
computable for injective functions from $[0,1]$ to $\IR$
<cit.>, its complexity is linked to the existence of one-way
functions from dimension two onwards <cit.>.
If, however, $f$ is bi-Hölder continuous (, both $f$ and its
inverse are Hölder continuous), then $\dsoinv$ still is only
computable in exponential time, but becomes
parameterized polynomial-time computable for
bi-Lipschitz functions (<ref>).
It turns out that this bound is actually the best we can achieve:
There is no parameterized polynomial-time algorithm for $\dsoinv$ over
bi-Hölder functions that are not bi-Lipschitz assuming that one-way
permutations exist (<ref>; an assumption stronger than
the existence of one-way functions).

We start to formally prove the above claims by reviewing a few non-uniform
bounds on function inversion.
The first fact is a uniform reformulation of the above mentioned inversion
result, <cit.>, for one-dimensional functions.

$\dsoinv$ is polynomial-time
$\big( \invrep[1,1][{[0,1]}], \parinvrep[1,1][\IR] \big)$-computable.

Notice the necessity of adding an inverse modulus $\modsu$ to make this
result work.
The algorithm behind the proof is based on binary search on $[0,1]$:
For a given point $q$ in the range of $f$, start with $p = 1/2$ as a candidate
for a $2^{-n}$-approximation to $f^{-1}(q)$ and use that injectivity implies
strict monotonicity for injective functions $f \colon [0,1] \to \IR$ to
determine whether to continue this binary search in $[0,p]$ or $[p,1]$.
This algorithm stops and returns $p$ when it is of precision roughly
$\modcont(\modsu(n))$. By unrolling the definitions of both $\modcont$ and
$\modsu$ one verifies that this indeed gives a $2^{-n}$-approximation to
This approach, however, fails from dimension two onwards since binary search
is no longer permitted due to the lack of monotonicity.

The following two results recall known lower and upper bounds on the
complexity of non-uniform function inversion.

[non-uniform bounds for function inversion;

* If $\PTime = \NPTime$, then $f^{-1}$ is polynomial-time
$(\realrep[2],\realrep[2])$-computable on $\range(f)$
whenever $f \colon [0,1]^2 \to \IR^2$ is injective,
$(\realrep[2]|^{[0,1]^2},\realrep[2])$-computable in polynomial time
and $\modsu$ is polynomially bounded.[Note that $f$ being
polynomial-time computable already implies $\modcont$ to be
polynomially bounded.]

* If $\PTime \neq \UPTime$, then there exists a function
$f \colon [0,1]^2 \to [0,1]^2$ for whom $f^{-1}$ is not
$(\realrep[2],\realrep[2])$-computable in polynomial time on
$\range(f)$ even if $f$ is injective, polynomial-time
$(\realrep[2],\realrep[2])$-computable and if $\modsu$ is
polynomially bounded.

The second statement has been proved using the following result that connects
the $\PTime$ vs. $\UPTime$ question with the existence of
one-way functions
(which we discus thereafter).

Total one-way functions exist if and only if
$\PTime \neq \UPTime$.

Notice the emphasis on totality (and implicitly on injectivity) since there
are other types of one-way functions whose existence, in contrast, are not
always connected to just $\PTime$ vs. $\UPTime$ <cit.>.
An injective polynomial-time computable function
$\phi \parcol \Sast \to \Sast$ is said to be a (worst-case)
one-way function if

* some polynomial $p$ exists such that
$\len{\phi^{-1}(s)} \leq p(\len{s})$ whenever $s \in \range(\phi)$
(polynomial honesty); and

* if no polynomial-time computable function $\psi$ satisfies
$\psi(\phi(s')) = s'$ for all $s' \in \dom(\phi)$ (not
polynomial-time invertible).

Now we are equipped to talk about the proof of <ref>(2):
Assume $\PTime \neq \UPTime$, and let $\phi \colon \Sast \to \Sast$ be a
total one-way function.
Based on $\phi$, construct a piecewise-linear function $f$ with the
properties described in <ref>(2) which is hard to invert if $\phi$ is.
This is achieved by encoding the image of $\phi$ into the domain of $f$ in a
way which only allows to recover the inverse $s = \phi^{-1}(t)$ from
$t$ and $f$ if $\phi$ is polynomial-time computable.
The moduli (of continuity/unicity) of $f$ are, moreover, polynomials.
More precisely, $\modcont(n) = \modsu(n) = cn + p(n) + \const$, where
$p(\len{s}) = \len{\phi^{-1}(s)}$ for any $s \in \Sigma^\ast$.
Since $p(n)$ is super-logarithmic[If not, one could just
try out all of the $2^{\lb(\len{s})}$ many possible preimages for
$s$ under $\phi$, thus computing $\phi$ in polynomial time,
contradicting the existence of one-way functions (since $\phi$ is
an arbitrary one), thus implying $\PTime = \UPTime$.],
the moduli are bounded linear (from below) in $n$. This suggests that
$\dsoinv$ could be polynomial-time computable for the class of Lipschitz-
or even Hölder-continuous functions; which we prove to be almost
correct in <ref>; and it can not be generalized to
arbitrary polynomially bounded moduli (<ref>(2)).

The inversion algorithm we devise in <ref> will be based on
knowledge about (a subset of) the domain of a given function. To this end,
a natural way to express the computation of $\dsoinv$ over representations
would be to pick one of the set representations introduced before alongside
with a representation of continuous functions; we choose $\setrep[d]$ and
$\invrep[d,e]$, and based on them we define a new representation
entailing the properties sufficient to state <ref>.

Let $f \parcol \IR^d \to \IR^{e}$ be a (possibly partial) function with
compact domain, and let $S \in \compset[d]$.
A $\enc{\phi,\modcont,\modsu,\psi} \in \Reg$ is a
$\setinvrep[d,e][\IR^d]$-name of $(f,S)$ if

* $S \subseteq \dom(f)$;

* $\psi$ is a $\gridrep[d]$-name of $S$;

* $\enc{\phi,\modcont,\modsu}$ is a $\parinvrep[d,e]$-name of $f$.

Recall that a function $f \colon X \to Y$ on normed spaces
$(X,\ndot[X])$ and $(Y,\ndot[Y])$ is $(\alpha,C)$-Hölder (continuous)
with Hölder exponent $0 < \alpha \leq 1$ and
Hölder constant $C > 0$ if it satisfies

\[
\norm[Y]{f(x)-f(y)} \leq C\cdot\norm[X]{x-y}^\alpha
\]

for any two $x,y \in X$.

In particular, an $(\alpha,C)$-Hölder function has modulus of continuity
$\modcont(n) \dfeq (n + \lb(C)) \cdot \alpha^{-1}$, and any $L$-Lipschitz
(continuous) function is in fact $(1,L)$-Hölder.
Take $[0,1] \ni x \mapsto \sqrt{x}$ as an example:
It is $(\alpha, 1)$-Hölder for $\alpha \leq 1/2$, and its inverse
$[0,1] \ni y \mapsto y^2$ is even $(1,1)$-Hölder (hence $1$-Lipschitz).

If the inverse of a Hölder function $f$ exists and if it moreover is a Hölder
function, than we call $f$ bi-Hölder.
If $f$ is bi-Hölder, then there exist bounds $0 < \alpha,\alpha' \leq 1$
and $C,C' > 0$ such that

\[
1/C' \cdot \norm[X]{x-y}^{1/\alpha'}
\leq \norm[Y]{f(x) - f(y)}
\leq C \cdot \norm[X]{x-y}^\alpha
\eqnsp .
\]

If $\alpha = \alpha' = 1$, then we call $f$ bi-Lipschitz.
Exponents $\alpha \in \{ 0 \} \cup (1,\infty)$ excluded by purpose:
$\alpha = 0$ if the respective function is bounded, and
$\alpha > 1$ if it is constant.

For convenience, denote by $\hfun$ the class of partial functions
$f \parcol \IR^d \to \IR^e$ that are also bi-Hölder, and by $\lfun$
the class of those $f$ being bi-Lipschitz.
Now we are equipped to state our result about inversion.

Operator $\dsoinv$ is $\big(\setinvrep[d,e],\parinvrep[e,d] \big)$-computable
and its time complexity
depends exponentially on $\modcont \circ \modsu \circ \modcont(n)$.
This exponential dependence still holds true when restricted to $\hfun$,
but leads to a parameterized polynomial-time bound when further
restricted to $\lfun$.

The exponential dependence on Hölder parameters in the above theorem is
actually optimal.
To see why, we consider the notion of one-way permutations,
that is, bijective one-way functions.
It is known by <cit.> that total one-way permutations exist if
and only if $\PTime \neq \UPTime \cap \co\UPTime$.
Recall that the moduli of the function specifically constructed to prove
<ref>(2) were polynomially bounded in $n$.
Assuming the existence of total one-way permutations, they even become
linear in $n$.
Noting that $f$ is a Hölder function if and only if it has a linearly bounded
modulus then implies the claimed optimality of <ref>.

Let $\varphi$ be a total one-way permutation.
Then a partial one-way permutation
$\psi \parcol \Sast \to \Sast$ with
the following properties can be constructed from $\varphi$:

* $\psi$ is length-preserving, ,
$\psi[\Sigma^m] \subseteq \Sigma^m$ for all $m \in \IN \eqnsp ;$

* $\psi \in \FPTime \eqnsp ;$

* $\psi^{-1} \in \FPTime \implies \varphi^{-1} \in \FPTime \eqnsp .$

Assume $\PTime \neq \UPTime \cap \co\UPTime$.
Then there exists a function $f \colon [0,1]^2 \to [0,1]^2$ for whom
$f^{-1}$ is not $(\realrep[2],\realrep[2])$-computable in polynomial
time on $\range(f)$ even if $f$ is injective, polynomial-time
$(\realrep[2],\realrep[2])$-computable and its moduli $\modcont,\modsu$
are of form $n \mapsto an+b$ with $a,b \in \IN$.

<Ref> leads to the conclusion that the exponential-time
bound in <ref> for $\dsoinv$ restricted to Hölder functions
is optimal (assuming $\PTime \neq \UPTime \cap \co\UPTime$) as a continuous
function is Hölder continuous if and only if it admits a linear modulus of

We now sketch how to prove <ref> (also illustrated in
<ref>) and postpone the respective proofs of the last two
statements until the end of this subsection.

Points $p_j$ along with their correct and approximate images
$f(p_j)$ and $q_j \dfeq \phi \big( p_j, 0^{m_i+1} \big)$,
respectively. All approximate images $q_j$, except for $q_2, q_3$ and
$q_9$, are close enough to $q$ (all that lies within the
blue-highlighted ball), thus being candidates of being an approximate
inverse image of $q$ in round $i+1$.

Let $q$ be the point to compute
$(f|_S)^{-1}(q)$ for. Testing for all points $p$ on a fine grid, say
$\ID^d_{k(n)}$, whether their image approximate image is close to $q$ would be
a pure brute-force approach, and as such having an exponential running time.
Instead we search iteratively:
Start with a coarse grid $\ID^d_{k(0)}$ and keep
all this points from this (coarse) grid whose images are not too far from $q$.
The key idea in this step, which will lead to a low(er) complexity, is that
the number of points that have to be kept in this step can be bounded in terms
of both moduli ($\modcont$ and $\modsu$):

* Any two distinct points $p,p' \in \ID^d_{\modcont(n)}$ are
$\norm{p - p'} > 2^{-(\modcont(n) + 1)}$ apart,

* thus (by definition of the inverse modulus) their images satisfy

\[
\cball\big( f(p), 2^{-\modsu(\modcont(n)+1)} \big) \cap
\cball\big( f(p'), 2^{-\modsu(\modcont(n)+1)} \big) = \emptyset
\]

* which implies that only finitely many points from a fixed grid can
be close to $q$ and we can bound their amount in terms of
$\modcont$, $\modsu$ and $n$.

For the next iteration, the grid will be refined to $\ID^d_{k(1)}$. But
instead of checking all these points, we will consider only those being close
to a point $p$ from the former grid $\ID^d_{k(0)}$ whose image has turned out
to be not too far from $q$. The complexity of this algorithm for finding a
good approximation to $f^{-1}(q)$ will then be of form
$\bigO(n \cdot \#\text{of points that has to be kept in each iteration})$.

Let $\enc{\phi, \modcont, \modsu, \phi', 0^b}$ be a $\parinvrep[d,e]$-name
of $(f,S)$.
Further, let $n \in \IN$ and $q \in \ID^e \cap S$;
we postpone the discussion about the general case where
$\dist{f[S]}(q) \leq 2^{-\modsu(n+1)}$ to a later stage in this proof.
Without loss of generality, we assume $\modcont(n+1)-\modcont(n) \geq 1$
and $\modsu(n+1)-\modsu(n) \geq 1$.[
Hölder functions with Hölder exponent $\alpha \in (0,1]$
have this property since
$\mu(n+1)-\mu(n) = 1/\alpha \in [1,\infty)$
for $\mu(n) = 1/\alpha \cdot (n + \lb{H})$.
Moreover, we prove the theorem only for $b \dfeq 0$ (just for convenience)
although the arguments extend to arbitrary outer radii parameter $b$.

To shorten the frequently used terms, we define precisions
$k_i \dfeq \modcont(\modsu(i)+1)+1$ and $m_i \dfeq \modsu(i)$, radii
$r_i \dfeq 2^{-k_i+1}$ and $t_i \dfeq 2^{-m_i}$, as well as approximations
$q_{p,i} \dfeq \phi(p,0^{k_i})$.
The proof is centered around the following sets:

\begin{align*}
S_{0} & \dfeq \st{p \in \ID^d_{k_0}}{\phi'(p,0^{m_0}) = 1}
\eqnsp , \\
C_{i} & \dfeq \st[1]{p \in S_i}{
p \in S_i \text{ and } \norm{q - q_{p,i}} \leq 2 t_i
\eqnsp , \\
S_{i+1} & \dfeq \bigcup_{p \in C_i} S_{p,i+1}
\eqnsp , \quad
S_{p,i+1} \dfeq \st[1]{p' \in \cball(p,r_i) \cap \ID^d_{k_{i+1}}}{
\phi'(p',0^{m_{i+1}}) = 1}
\eqnsp .
\end{align*}

All we now have to do is to iteratively compute the candidate sets
$C_i$ and finally deterministically pick a point $p \in C_{n+2}$.
We claim that such a $p$ exists and that it is a $2^{-n}$-approximation to

An important note before we continue.
Since $f$ is a partial function the term “$f(p)$” might be undefined for
some $p \in S_i$.
We nontheless want to talk about objects like “$\cball(f(p),\cdot)$”.
The definition of $\invrep[d,e]$ solves this problem:
For $i \in \IN$ and $p \in \ID^d_{k_i}$ let $x_{p,i}$ be any
point from $S \cap \cball(p,r_i)$ as in eqn:cond-partial.
Then $f\big[\cball(p,r_i) \cap S\big] \subseteq \cball(f(x_{p,i}),t_i)$,
and we will therefore always reason about $\cball(f(x_{p,i}),\delta)$
instead of the maybe undefined $\cball(f(p),\delta/2)$.

We have to show that $C_i \neq \emptyset$ for all $0 \leq i \leq n+2$, and
that $f^{-1}(q) \in \cball(p,2^{-n})$ for any $p \in C_{n+2}$.
Instead of the statment “$C_i \neq \emptyset$” we prove the stronger
proposition “$\xsome{p_i}{C_i} q \in \cball(f(x_{p_i,i}),t_i)$”.

For $i=0$ we first note that $\bigcup_{p \in S_0} \cball(p,r_0)$ is a
superset of $S$.
This plus the definition of $\modcont$ imply
$f[S] \subseteq \bigcup_{p \in S_0} \cball(f(x_{p,0}),t_0)$.
Therefore, there must exist a point $p_0 \in S_0$ whose image is close to $q$
in the sense that $q \in \cball(f(x_{p_0,0}),t_0)$.
Hence, $\norm{q - q_{p_0,0}} \leq 2t_0$ which gives $C_0 \neq \emptyset$.

Now let $i \geq 1$.
By construction of $C_{i-1}$ and $S_i$ it holds that

\[
q \in
\bigcup_{p \in C_{i-1}} f\big[ \clb{p}{r_{i-1}} \cap S \big]
\subseteq
\bigcup_{p \in C_{i-1}} \bigcup_{p' \in P_{p,i}}
f\big[ \clb{p'}{r_i} \cap S \big]
\eqnsp .
\]

Therefore the exists a $p' \in P_i$ with $\norm{q - f(x_{p',i})} \leq t_i$,
implying $\norm{q - q_{p',i}} \leq 2t_i$.
Thus, $C_i \neq \emptyset$.

In the end (, for $i = n+2$), the definition of $\modsu$ implies that for
any $p \in C_{n+2}$ holds $q \in \cball(q_{p,n+2},2t_{n+2})$, which first
leads to $q \in \cball(f(x_{p,n+2}),3t_{n+2})$.
Using that $\modsu(n+2) - \modsu(n) \geq 2$ implies
$3t_{n+2} < 4t_{n+2} \leq t_n$
finally allows to conclude $f^{-1}(q) \in \cball(p,2^{-n})$.

A note on the general case of $\dist{f[S]}(q) \leq t_{n+1}$:
By assumption, there exists an $x \in S$ such that
$\norm{f(x) - q} \leq t_{n+1}$.
Therefore, $\norm{f(x) - f(x_{p,n+2})} \leq t_{n+2}$ holds true for all
$p \in \ID^d_{k_{n+2}} \cap \clb{x}{r_{n+2}}$, implying
$\norm{f(x) - q_{p,n+2}} \leq 2t_{n+2}$.
Combining both bounds then gives
$\norm{q_{p,n+2} - q} \leq 4t_{n+2} \leq t_{n}$.

We have to bound the number of points in $S_{0}, C_i$ and $S_{i+1}$ for
$i \in \IN$.
The set $S_{0}$ contains at most $2^{d(b + k_0)}$ many points[
This is true modulo details:
The exponential dependence on $k_0 = \modcont(\modsu(0)+1)+1$ only leads
to an exponential dependence on the respective Hölder exponents.
This exponential bound, however, can be reduced to linear:
Extend the definition of $\modcont$ and $\modsu$ to integers and,
instead of $k_0$, start with $k_{-j}$ for $j \in \IN_+$ being maximal
with property $k_{-j} \geq 0$.
Such a $j$ can be found in time logarithmic in the absolute value of
both Hölder constants.
and $|S_{i+1}|$ is bounded by

\[
\leq \sum_{p \in C_i} \big| \cball(p,r_i) \cap \ID^d_{k_{i+1}} \big|
\leq |C_i| \cdot (2r_i/r_{i+1})^d
\leq |C_i| \cdot 2^{d(k_{i+1} - k_i + 2)}
\eqnsp .
\]

The bound on $|C_i|$ requires a bit more care (as hinted prior to this proof):
Any two distinct points $p,p' \in C_i$ have the property that
$\cball(p,r_i/4)$ and $\cball(p',r_i/4)$ are disjoint.
It then follows by definition of $\modsu$ that
$\cball(x_{p,i},2^{-\modsu(k_i+2)})$ and $\cball(x_{p',i},2^{-\modsu(k_i+2)})$
are also disjoint.
This fact now allows to bound $|C_i|$ by counting how many disjoint
balls of radius $2^{-\modsu(k_i+2)}$ fit into $\clb{q}{2t_i+t_i}$:

\[
\leq (2 \cdot 3t_i/2^{-\modsu(k_i+2)})^d
< (4 \cdot 2^{\modsu(k_i+2) - m_i})^d
\eqnsp .
\]

The above describe procedure for computing $\dsoinv$ therefore checks at most

\begin{align*}
\bigO\Big(
\sum_{i=0}^{n+2}\nolimits \big|C_i\big| + \big|S_i\big|
\Big)
\end{align*}

which is bounded by (and thus further simplifies to)

\begin{align}
\label{eqn:inv-cpl-bound-general}
\bigO\big(