Towards Computational Complexity Theory on Advanced Function Spaces in Analysis

Abstract

Pour-El and Richards [PER89], Weihrauch [Weih00], and others have extended Recursive Analysis from real numbers and continuous functions to rather general topological spaces. This has enabled and spurred a series of rigorous investigations on the computability of partial differential equations in appropriate advanced spaces of functions. In order to quantitatively refine such qualitative results with respect to computational efficiency we devise, explore, and compare natural encodings (representations) of compact metric spaces: both as infinite binary sequences (TTE) and more generally as families of Boolean functions via oracle access as introduced by Kawamura and Cook ([KaCo10], Sect. 3.4). Our guide is relativization: Permitting arbitrary oracles on continuous universes reduces computability to topology and computational complexity to metric entropy in the sense of Kolmogorov. This yields a criterion and generic construction of optimal representations in particular of (subsets of) $L^p$ and Sobolev spaces that solutions of partial differential equations naturally live in.

Supported in part by JSPS Kakenhi projects 24106002 and 26700001, by EU FP7 IRSES project 294962, by DFG Zi 1009/4-1 and by IRTG 1529. We thank Daniel Graça and Elvira Mayordomo for inviting this extended abstract as opportunity to report on our progress since its CCA 2015 short version.

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1 Introduction and Motivation

The Type-2 Theory of Effectivity (TTE) compares and studies transformation properties of so-called representations for a given space X: surjective partial mappings $\delta :\subseteq \{\texttt {0} ,\texttt {1} \}^\omega \rightarrow X$ describing an encoding of X’s elements as infinite binary strings, such as sequences of (indices of) fast converging approximations from a fixed countable dense subset. In particular several natural but different representations of spaces of continuous functions on Euclidean domains have been established as computably equivalent. Partial differential equations, however, exhibit counter-intuitive computability properties when considered on such classical function spaces rather than than the advanced ones suggested by functional analysis: $L^p$ and more generally Sobolev spaces $W^k_p$ [WeZh02]. The qualitative computability theory of such spaces is well established [SZZ15]; and we, taking a refined complexity-theoretic perspective, suggest, and justify the choice of, natural representations promising to bridge the gap to numerical practice.

Section 2 recalls notions and qualitative topological characterizations of relatively computable functions on metric spaces. Section 3 collects quantitatively refined notions under time and space bounds. Section 4 reports on Kolmogorov’s entropy of a compact metric space. And Sect. 5 connects the latter two in terms of ‘ordinary’ and second-order representations, the latter introduced in [KaCo10, Sect. 3.4] and recalled in Sect. 6. Justified by these considerations, Sect. 7 finally introduces a natural second-order representation for Sobolev spaces. Proofs are deliberately omitted from this expository abstract.

2 Computing on Separable Metric Spaces

Similarly to the classical theory of computing encoding discrete structures (graphs, integers etc.) as finite binary strings, the Type-2 Theory of Effectivity (TTE) studies, and compares notions of, computation over continuous universes by encoding as infinite binary strings. The following concepts are essentially from [Weih00, Sect. 2.1+Sect. 2.3+Sect. 3.1+Sect. 8.1], Item f) from [Schr95]; cmp. also [PER89, Sect. 2].

Definition 1

• (a) An Oracle Type-2 Machine $\mathcal {M}^O$ is a Turing machine with read-only input tape, read-write working tape, and one-way output tape as well as access to the — possibly empty — oracle $O\subseteq \{\texttt {0} ,\texttt {1} \}^*$ by means of one-way query tape. $\mathcal {M}^O$ is said to compute the partial function $F:\subseteq \{\texttt {0} ,\texttt {1} \}^\omega \rightarrow \{\texttt {0} ,\texttt {1} \}^\omega$ if, on input $\bar{w}\in {\text {dom}}(F)$, it prints $F(\bar{w})$. Its behaviour on $\bar{w}\not \in {\text {dom}}(F)$ may be arbitrary.

• (b) A representation of a space X is a partial surjective mapping $\xi :\subseteq \{\texttt {0} ,\texttt {1} \}^\omega \twoheadrightarrow X$. A $\bar{w}$ with $\xi (\bar{w})=x$ is a $\xi$-name of $x\in X$.

• (c) A partial multivalued mapping $f:\subseteq X\rightrightarrows Y$ is a relation $f\subseteq X\times Y$, considered as total function $f:X\ni x\mapsto \{y\in Y:(x,y)\in f\}$. Its domain is ${\text {dom}}(f)=\{x: f(x)\ne \emptyset \}$. A (partial) single-valued mapping is considered as multivalued with singleton (or empty) values.

• (d) For $\upsilon$ a representation of Y, a $(\xi ,\upsilon )$-realizer of f is a partial function $F:\subseteq \{\texttt {0} ,\texttt {1} \}^\omega \rightarrow \{\texttt {0} ,\texttt {1} \}^\omega$ with $\upsilon \circ F\subseteq f\circ \xi$. Call $f:\subseteq X\rightrightarrows Y$ relativized $(\xi ,\upsilon )$-computable iff there exists an oracle type-2 machine $\mathcal {M}^O$ computing some $(\xi ,\upsilon )$-realizer of f. We omit $\xi ={\text {id}}$ in case $X=\{\texttt {0} ,\texttt {1} \}^\omega$.

• (e) A presented separable metric space is a triple $(X,d,\xi )$, where X denotes the carrier set with metric $d:X\times X\rightarrow [0;\infty )$ and $\xi :\subseteq \mathbb {N}\rightarrow X$ a partial enumeration of some dense ${\text {image}}(\xi )\subseteq X$.

• (f) For a presented separable metric space $(X,d,\xi )$, a $\xi$-name of $x\in X$ is an integer sequence $(a_m)_{_m}$ satisfying

  $$\begin{aligned} \forall m: \qquad a_m\in {\text {dom}}(\xi ) \;\;\wedge \;\; d\big (\xi (&a_m),x\big )<2^{-m} \;\;\wedge \;\; \nonumber \\&\wedge \; \forall a'<a_m: d\big (\xi (a'),x\big )\ge 2^{-m-1} . \end{aligned}$$

  (1)

  The induced representation of $(X,d,\xi )$ is the partial mapping (abusing names also denoted by) $\xi :\subseteq \{\texttt {0} ,\texttt {1} \}^\omega \twoheadrightarrow X$ with $\big \langle \big ({\text {bin}}(a_m)\big )_{m}\big \rangle \mapsto x$ for every $\bar{a}=(a_m)_{_m}$ satisfying Eq. (1).

• (g) Here we denote by ${\text {bin}}$ both the binary expansion

  $$ {\text {bin}}:\{\texttt {0} ,\texttt {1} \}^*\;\ni \;(v_0,\ldots ,v_{J-1})\;\mapsto \;2^J-1+\sum \nolimits _{j=0}^{J-1} v_j2^j \;\in \;\mathbb {N}$$

  and its inverse, where $\mathbb {N}=\{0,1,2,\ldots \}$. Furthermore write

  $$\begin{aligned} \langle (v_1,\ldots ,v_n)\rangle \;:=\;(\texttt {1} ,v_1,\texttt {1} ,v_2,\ldots ,\texttt {1} ,v_{n-1},\texttt {0} ,v_n) \end{aligned}$$

  for the binary string encoding with delimiter; and also for pairing functions

  $$ (\{\texttt {0} ,\texttt {1} \}^*)^*\ni \big (\vec v^{(1)},\ldots ,\vec v^{(k)}\big ) \mapsto \langle \vec v^{(1)}\rangle \,\ldots \,\langle \vec v^{(k)}\rangle \in \{\texttt {0} ,\texttt {1} \}^* $$

  and $(\{\texttt {0} ,\texttt {1} \}^*)^*\times \{\texttt {0} ,\texttt {1} \}^\omega \rightarrow \{\texttt {0} ,\texttt {1} \}^\omega$ and $(\{\texttt {0} ,\texttt {1} \}^*)^\omega \rightarrow \{\texttt {0} ,\texttt {1} \}^\omega$. Finally abbreviate $[N]:=\{0,\ldots ,N-1\}$ for $N\in \mathbb {N}$; let $\vec v_{<n}$ and $\bar{v}_{<n}$ mean the first n symbols of $\vec v\in \{\texttt {0} ,\texttt {1} \}^{n+m}$ and of $\bar{v}\in \{\texttt {0} ,\texttt {1} \}^\omega$, respectively; write $\vec v_n$ and $\bar{v}_n$ for the n-th symbol.

• (h) For metric spaces (X, d) and (Y, e) a mapping $\mu :\mathbb {N}\rightarrow \mathbb {N}$ is a modulus of continuity to the function $f:X\rightarrow Y$ if, for every $m\in \mathbb {N}$ and $x,x'\in X$, $d(x,x')<2^{-\mu (m)}$ implies $e\big (f(x),f(x')\big )<2^{-m}$. We write ${\text {B}}(x,r):=\{x'\in X:d(x,x')<r\}$ for the open ball of radius $r\ge 0$ around $x\in X$ and $\bar{{\text {B}}}(x,r):=\{x'\in X:d(x,x')\le r\}$ for the corresponding closed ball.

Our prototype presented metric space is the real unit interval $X=[0;1]$ equipped with $\rho :\mathbb {N}\rightarrow X$ enumerating the dyadic rationals $\{0,(2\tilde{a}+1)/2^m:\mathbb {N}\ni \tilde{a}\le 2^{m-1},m\in \mathbb {N}_+\}$ in [0; 1) without repetition in ‘lexicographical’ order: $0,\tfrac{1}{2},\tfrac{1}{4},\tfrac{3}{4},\tfrac{1}{8},\tfrac{3}{8},\tfrac{5}{8},\tfrac{7}{8},\tfrac{1}{16},\ldots$; cmp. [BrCo06]. Computing on continuous universes combines recursion-theoretic and topological aspects, reducing to the latter when permitting access to arbitrary oracles; cmp. Items (b+c) of the following

Fact 2

• (a) A function $f:X\rightarrow Y$ admits a modulus of continuity iff it is uniformly continuous. On bounded X, f is Hölder continuous iff it admits a linear modulus of continuity.

• (b) A partial function $F:\subseteq \{\texttt {0} ,\texttt {1} \}^\omega \rightarrow \{\texttt {0} ,\texttt {1} \}^\omega$ is continuous iff it is computable by some oracle type-2 machine.

• (c) Let $(X,d,\xi )$ and $(Y,d,\upsilon )$ denote presented metric spaces. A partial function $f:\subseteq X\rightarrow Y$ is continuous iff it is relativized $(\xi ,\upsilon )$-computable.

• (d) Reciprocals $(0;1]\ni x\mapsto 1/x$ are $(\rho ,\rho )$-computable but, lacking uniform continuity, not within bounded time nor space.

• (e) A partial function $f:\subseteq [0;1]\rightarrow \mathbb {R}$ admits a polynomial modulus of continuity iff it is $(\rho ,\rho )$-computable by some polynomial-time oracle type-2 machine.

• (f) The continuous function $h_{\exp }:[0;1]\ni x\mapsto 1/\ln (e/x)$ is computable (without oracle) in exponential time but, lacking a polynomial modulus of continuity, not (even with oracle) in sub-exponential time.

• (g) A partial $F:\subseteq \{\texttt {0} ,\texttt {1} \}^\omega \rightarrow \{\texttt {0} ,\texttt {1} \}^\omega$ admits a polynomial modulus of continuity iff it is computable by some polynomial-time oracle type-2 machine.

• (h) There is no representation $\delta :\subseteq \{\texttt {0} ,\texttt {1} \}^\omega \twoheadrightarrow {\text {Lip}}_1\big ([0;1],[0;1]\big )$ of the compact space of uniformly bounded and equicontinuous functions $f:[0;1]\rightarrow [0;1]$ with $|f(x)-f(x')|\le |x-x'|$ rendering application $(f,x)\mapsto f(x)$ uniformly $(\delta \times \rho ,\rho )$-computable in relativized subexponential time.

Item (a) is from [KSZ14, Example 2.5], for (b) see [Weih00, Theorems 2.3.7+2.3.8], and for (c) confer [Weih00, Theorem 3.2.11+Definition 3.1.3]. The latter has been generalized from metric to topological so-called QCB-spaces [Schr06, Theorem 2], to weaker representations, as well as from continuity to (levels of Borel) measurability [Zieg07, dBYa10]. For (d) see for instance [Weih00, Theorem 4.3.2.6+Example 7.2.8.3]. [Ko91, Theorem 2.19] asserts one direction of (e) for total functions $f:[a;b]\rightarrow \mathbb {R}$. Regarding (f) consider [KMRZ15, Fact 3g]; and Lemma 6.3 in [PaZi13] for (g). Claim (h) is contained in [Weih03, Sect. 6]; see also [FHHP15, Theorem 3.1].

3 Computational Complexity on Compact Metric Spaces

Items (d) to (h) of Fact 2 refer to the following notions:

Definition 3

• (a) For $t:\mathbb {N}\rightarrow \mathbb {N}$, an oracle type-2 machine $\mathcal {M}^O$ computing $F:\subseteq \{\texttt {0} ,\texttt {1} \}^\omega \rightarrow \{\texttt {0} ,\texttt {1} \}^\omega$ does so in time t(m) if it prints the m-th symbol of $F(\bar{v})$ after at most t(m) steps for every $\bar{v}\in {\text {dom}}(F)$. F is relativized polynomial-time computable if there exists some $d\in \mathbb {N}$ and an oracle type-2 machine computing it in time $t(m)=d\cdot (1+m^d)$.

• (b) For $s:\mathbb {N}\rightarrow \mathbb {N}$, an oracle type-2 machine $\mathcal {M}^O$ computing $F:\subseteq \{\texttt {0} ,\texttt {1} \}^\omega \rightarrow \{\texttt {0} ,\texttt {1} \}^\omega$ does so in space s(n) if it prints the m-th symbol of $F(\bar{v})$ after using at most s(m) cells of the working tape (and ’arbitrary’ amounts of the input, output, and query tapes) for every $\bar{v}\in {\text {dom}}(F)$.

• (c) Fix $s,t:\mathbb {N}\rightarrow \mathbb {N}$ and a (possibly partial and multivalued) function $f:\subseteq X\rightrightarrows Y$ between represented space $(X,\xi )$ and presented metric space $(Y,e,\upsilon )$. An oracle type-2 machine $(\xi ,\upsilon )$ -computes f in time t(m) and space s(m) iff it, for every input of any $\bar{v}\in {\text {dom}}(\xi )$ with $\xi (\bar{v})\in {\text {dom}}(f)$, produces an $\upsilon$-name $\big \langle \big ({\text {bin}}(w_m)\big )_{m}\big \rangle$ of some $y\in f(x)$ such that ${\text {bin}}(w_m)\in \{\texttt {0} ,\texttt {1} \}^*$ appears on the output tape within $\le t(m)$ steps and using $\le s(m)$ cells of the working tape.

• (d) The time and/or space of a machine according to (c) is bounded if there exist mappings t and/or s as above. It is logarithmic/polynomial/exponential if such mappings can be chosen to have asymptotic growth bounded by $\mathcal {O}(\log m)$, ${\text {poly}}(m):=\mathcal {O}(m)^{\mathcal {O}(1)}$, and $2^{{\text {poly}}(m)}$, respectively.

• (e) A representation $\xi$ of X is polynomially admissible if for every representation $\delta$ of X the following holds: $\delta :\subseteq \{\texttt {0} ,\texttt {1} \}^\omega \twoheadrightarrow X$ has a polynomial modulus of continuity  iff  there exists a mapping $F:{\text {dom}}(\delta )\rightarrow {\text {dom}}(\xi )\subseteq \{\texttt {0} ,\texttt {1} \}^\omega$ with polynomial modulus of continuity such that $\delta =\xi \circ F$.

• (f) The product $\xi \times \upsilon$ of $\xi :\subseteq \{\texttt {0} ,\texttt {1} \}^\omega \twoheadrightarrow X$ and $\upsilon :\subseteq \{\texttt {0} ,\texttt {1} \}^\omega \twoheadrightarrow Y$ is the mapping

  $$ \{\texttt {0} ,\texttt {1} \}^\omega \;\ni \; (w_0,w_1,w_2, w_3,\ldots )\;\mapsto \big (\xi (w_0,w_2,\ldots ),\upsilon (w_1,w_3,\ldots )\big ) \;\in \; X\times Y .$$

• (g) A mapping $f:X\rightarrow Y$ between topological spaces is proper if the pre-images $f^{-1}[K]=\{x\in X:f(x)\in K\}\subseteq X$ of compact sets $K\subseteq Y$ are compact.

Item (e) refines the well-known qualitative condition of computable admissibility [Schr06]; see [Weih00, Theorem 3.2.9]. For $X=\{\texttt {0} ,\texttt {1} \}^\omega =Y$ condition (c) boils down to (a) and (b), but for other represented spaces it may be unrelated to that of computing a $(\xi ,\upsilon )$-realizer within the given resource bounds [Weih00, Examples 7.2.1+7.2.3]: $\xi$ and $\upsilon$ could require/admit very long/short initial segments of names before reaching precision $2^{-m}$. Moreover, said precision is to be met within the given resource bound, regardless of the argument. To avoid counter-examples like Fact 2(d) we focus on proper representations of compact spaces; compare [Schr95, Weih03, Schr04] and [Weih00, Exercise 7.1.2].

4 Metric Entropy of Compact Metric Spaces

Theorem 6 will generalize Items (e) and (g) in Fact 2, and the complexity-theoretic characterizations of Items (f) and (h) from Cantor space and the real unit interval to certain compact metric spaces in the spirit of Fact 2(c), based on the following notions essentially dating back to Andrey N. Kolmogorov:

Definition 4

Fix a bounded metric space (X, d).

• (a) For $\varepsilon >0$ let ${\mathcal {C}}(X,d,\varepsilon ) \;:=\; \sup \big \{{\text {Card}}(C)\;\big |\;C\subseteq X,\; \forall x,x'\in C \;: \; x=x' \vee d(x,x')\ge \varepsilon \big \}$ denote the size of a largest collection of points fitting into X while avoiding each other by at least distance $\varepsilon$.

• (b) For $\varepsilon >0$ let ${\mathcal {H}}(X,d,\varepsilon ) \;:=\; \inf \big \{{\text {Card}}(C)\;\big |\;C\subseteq X,\; \forall x\in X\;\exists c\in C \;:\; d(x,c)<\varepsilon \big \}$ denote the least number of open balls of radius $\varepsilon$ covering X.

• (c) The capacity $\lceil (X,d)\rceil :\mathbb {N}\rightarrow \mathbb {N}$ of (X, d) is the truncated binary logarithm of $n\mapsto {\mathcal {C}}(X,d,2^{-n})$; i.e. X admits $2^{\lceil X\rceil (n)}$, but not $2^{\lceil X\rceil (n)+1}$, points of pairwise distance $\ge 2^{-n}$.

• (d) Dually, the entropy $\lfloor (X,d)\rfloor :\mathbb {N}\rightarrow \mathbb {N}$ of (X, d) is the truncated binary logarithm of $n\mapsto {\mathcal {H}}(X,d,2^{-n})$; i.e. X can be covered by $2^{\lfloor X\rfloor (n)}$ open balls of radius $2^{-n}$, but not by $2^{\lfloor X\rfloor (n)-1}$.

Compare for instance [KoTi59] or [Weih03, Sect. 6] and the related notion of a modulus of total boundedness [Kohl08, Definition 17.106]. Lemma 5(a) asserts that $\lceil X\rceil$ and $\lfloor X\rfloor$ have equal asymptotic growth as long as either one is at most exponential, i.e. $\le 2^{{\text {poly}}(n)}$: such as, e.g., $C_\mu (Y,[0;1])$ for both $\mu$ and $\lceil Y\rceil$ polynomials according to Item d) of the following

Lemma 5

• (a) Suppose $C\subseteq X$ is maximal w.r.t. $\subseteq$ satisfying $\forall x,x'\in C: \; x=x' \vee d(x,x')\ge \varepsilon$. Then $\bigcup _{c\in C}{\text {B}}(c,\varepsilon )=X$. For (X, d) totally bounded, ${\mathcal {C}}(X,d,\cdot )$ and ${\mathcal {H}}(X,d,\cdot )$ are non-increasing total functions $(0;\infty )\rightarrow \mathbb {N}$ satisfying ${\mathcal {H}}(X,d,\varepsilon )\le {\mathcal {C}}(X,d,\varepsilon )\le {\mathcal {H}}(X,d,\varepsilon /2)$. In particular it holds $\lfloor (X,d)\rfloor (n)\le \lceil (X,d)\rceil (n)\le \lfloor (X,d)\rfloor (n+1)$.

• (b) The finite set $X:=\{1,2,\ldots ,2^k\}$ of integers has constant capacity and entropy $\lceil X\rceil (n)\equiv k\equiv \lfloor X\rfloor (n)$. The Euclidean cube/torus $[0;2^k)^d$, equipped with the maximum norm, has capacity $\big \lceil [0;2^k)^d\big \rceil (n)=(n+k)\cdot d=\big \lfloor [0;2^k)^d\big \rfloor (n)$ and thus polynomial entropy.

• (c) The compact space from Fact 2(h) equipped with the supremum norm has asymptotically exponential capacity and entropy: $\big \lceil {\text {Lip}}_1\big ([0;1],[0;1]\big )\big \rceil (n) = \varTheta (2^n)$ $=$ $\big \lfloor {\text {Lip}}_1\big ([0;1],[0;1]\big )\big \rfloor (n)$. The same holds for ${\text {Lip}}_1\big ([0;1],[0;1]\big )\subseteq L^p$ equipped with the norm $f\mapsto \Vert f\Vert _p:=\root p \of {\int _0^1 |f(t)|^p\,dt}$ for any fixed $p\ge 1$.

• (d) Suppose totally bounded (X, d) has diameter ${\text {diam}}(X):=\sup \{d(x,x'):x,x'\in X\}\le 1$ and super-logarithmic yet at most exponential entropy $\lfloor X\rfloor :\mathbb {N}\rightarrow \mathbb {N}$. Moreover fix some strictly increasing $\mu :\mathbb {N}\rightarrow \mathbb {N}$. W.r.t. sup-norm the space    $C_\mu \big (X,[0;1]\big ) \;:=\; \big \{ f:X\rightarrow [0;1] \text { has modulus of continuity } \mu \big \}$    has $\log \big \lfloor C_\mu \big (X,[0;1]\big ) \big \rfloor (n)= \varTheta \Big (\lfloor X\rfloor \big (\mu \big (n\pm \varTheta (1)\big )\big )\Big )$. A set $Y\subseteq C(X,[0;1])$ is relatively compact iff it belongs to $C_\mu (X,[0;1])$ for some $\mu$.

• (e) Cantor space $2^\omega =\{\texttt {0} ,\texttt {1} \}^\omega$, equipped with the metric $\beta (\bar{v},\bar{w}):=2^{-\min \{n:v_n\ne w_n\}}$ has linear capacity $\lceil (2^\omega ,\beta )\rceil (n)=n+1$; equipped with the topologically equivalent metric $\beta '(\bar{v},\bar{w}):=1/(1+\min \{n:v_n\ne v_m\})$ on the other hand it has exponential capacity $\lceil (2^\omega ,\beta ')\rceil (n)=2^{n}-1$.

• (f) However whenever d and $d'$ are strongly equivalent metrics on X in the sense that $d'\cdot 2^{-c}\le d\le d'\cdot 2^c$ holds for some $c\in \mathbb {N}$ (such as in case X lives in some finite-dimensional normed real vector space), their induced capacities and entropies differ by at most a constant shift, i.e., it holds    $\forall n\ge c:$

  $$\begin{aligned} \lceil (X,d') \rceil (n-c)\le & {} \lceil (X,d) \rceil (n) \;\le \; \lceil (X,d') \rceil (n+c), \\ \lfloor (X,d') \rfloor (n-c)\le & {} \lfloor (X,d) \rfloor (n) \;\le \; \lfloor (X,d') \rfloor (n+c) \end{aligned}$$

• (g) Let (X, d) and (Y, e) be compact metric spaces and $f:X\rightarrow Y$ have modulus of continuity $\mu$. Then the image $f[X]\subseteq Y$ has entropy $\lfloor F[X]\rfloor \le \lfloor X\rfloor \circ \mu$.

Item (d) quantitatively refines the classical Arzelá-Ascoli Theorem; cmp. [Weih03, Theorem 6.7.3].

5 Relativized Complexity and Entropy

The entropy/capacity of compact metric spaces essentially determines the relativized computational complexity of functions on them:

Theorem 6

For a compact metric space (X, d) the following are equivalent:

• (i) X has polynomially bounded entropy: $\lfloor X\rfloor (m)\le p(m)$ for some $p\in \mathbb {N}[m]$.

• (ii) X has a proper representation $\delta :\subseteq \{\texttt {0} ,\texttt {1} \}^\omega \twoheadrightarrow X$ with polynomial modulus of continuity.

• (iii) X admits a representation $\delta$ rendering the following parameterized partial/fuzzy/ soft equality test relativized $\delta \times \delta$-computable in time polynomial in m:

  $$\begin{aligned} X\times X\times \mathbb {N}\;\ni \; (x,y,m) \;\mapsto \texttt {1} ^\omega \text { for } x=y, \quad \mapsto \texttt {0} ^\omega \text { for } d(x,y)\ge 2^{-m}. \end{aligned}$$

  (2)

• (iv) There exists a representation $\delta$ of X rendering Equation (2) relativized $\delta \times \delta$-computable in space logarithmic in m.

• (v) There exists a representation $\delta$ of X rendering the metric $d:X\times X\rightarrow [0;\infty )$ relativized $(\delta \times \delta ,\rho )$-computable in polynomial time

• (vi) or in logarithmic space.

• (vii) There exists a representation $\delta$ of X and polynomial $q\in \mathbb {N}[m]$ such that every 1-Lipschitz function $f:X\rightarrow [0;1]$ is relativized $(\delta ,\rho )$-computable in time q(m)

• (viii) or space $\mathcal {O}\big (\log q(m)\big )=\mathcal {O}(\log m)$.

Perhaps surprisingly, the same holds with $\delta$ replaced, in Items (iii) to (viii), by a second-order representation $\varDelta$ of X in the following sense:

6 Second-Order Complexity Theory

According to Fact 2(h) compact space ${\text {Lip}}_1([0;1],[0;1])$ does not admit a complexity-wise reasonable representation, i.e., encoding as infinite binary strings $\{\texttt {0} ,\texttt {1} \}^\omega \cong 2^{\{\texttt {1} \}^*}$: essentially due to their restriction to sequential access which requires ‘skipping’ over the f’s (approximate) values at many arguments $f(x')$ before reaching the desired f(x); whereas function arguments in practice provide oracle-like random access to their values. This has been formalized by encoding real function arguments as oracles [KaCo10].

Remark 7

Classical oracles are decision problems $O\subseteq \{\texttt {0} ,\texttt {1} \}^*$, that is, they return a single bit. Function oracles on the other hand return finite strings, that is, they correspond to elements of Baire space $\mathbb {N}^\mathbb {N}$ encoded in binary as mappings $\varphi :\{\texttt {0} ,\texttt {1} \}^*\rightarrow \{\texttt {0} ,\texttt {1} \}^*$. Now if the answer $\vec w=\varphi (\vec v)$ to a query $\vec v$ is ‘long’, an oracle machine $\mathcal {M}^{\varphi }$ arguably should be allotted more time than the same when run with an oracle $\psi$ giving ‘short’ answers. This leads to second-order polynomial resource bounds; see [KaCo96]. Function oracles of polynomial length, on the other hand, can be encoded into decision oracles queried bitwise (and in particular satisfying effective polynomial boundedness [KaPa15]).

For the purpose of this work we focus on the latter:

Definition 8

• (a) A second-order representation of a space X is a partial surjective mapping $\varXi :\subseteq 2^{\{\texttt {0} ,\texttt {1} \}^*}\twoheadrightarrow X$, where $2^Y$ denotes the set of all subsets $O\subseteq Y$, each identified with its characteristic function $\mathbf {1}_{O}:Y\rightarrow \{\texttt {0} ,\texttt {1} \}$.

• (b) An oracle Type-2 machine with variable/generic oracle is called contingent and denoted $\mathcal {M}^?$. It computes a partial function $F:\subseteq 2^{\{\texttt {0} ,\texttt {1} \}^*}\times \{\texttt {0} ,\texttt {1} \}^\omega \rightarrow \{\texttt {0} ,\texttt {1} \}^\omega$ if, for every $(O,\bar{v})\in {\text {dom}}(F)$, $\mathcal {M}^{O}$ on input $\bar{v}$ prints $F(O,\bar{v})$. It does so in logarithmic/polynomials/exponential time/space if the n-th symbol of $F(O,\bar{v})$ appears within such resource bounds of time/work tape cells, independently of $(O,\bar{v})\in {\text {dom}}(F)$ while permitting unbounded use of the input, output, and query tapes. More precisely $\mathcal {M}^?$ may peruse a fixed-depth stack of write-only query tapes where an oracle call refers to, and purges, the top one.

• (c) Fix a second-order represented space $(X,\varXi )$, (first-order) represented space $(Y,\upsilon )$, and presented metric space $(Z,e,\zeta )$ with induced representation $\zeta$. A contingent oracle machine $\mathcal {M}^?$ $(\varXi ,\upsilon ,\zeta )$-computes $f:\subseteq X\times Y\rightrightarrows Z$ in time t(m) and space s(m) iff, for every $O\in {\text {dom}}(\varXi )$ and $\bar{v}\in {\text {dom}}(\upsilon )$ with $\big (\varXi (O),\upsilon (\bar{v})\big )\in {\text {dom}}(f)$, $\mathcal {M}^O$ on input $\bar{v}$ produces a $\zeta$-name $\big \langle \big ({\text {bin}}(w_m)\big )_{m}\big \rangle$ of some $z\in f\big (\varXi (O),\upsilon (\bar{v})\big )$ such that ${\text {bin}}(w_m)\in \{\texttt {0} ,\texttt {1} \}^*$ appears on the output tape within at most t(m) steps and using at most s(m) cells of the working tape (and again ’arbitrary’ amounts of the input, output, and query tapes).

• (d) For second-order representations $\varXi :\subseteq 2^{\{\texttt {0} ,\texttt {1} \}^*}\twoheadrightarrow X$ and $\Upsilon :\subseteq 2^{\{\texttt {0} ,\texttt {1} \}^*}\twoheadrightarrow Y$, their (binary) product $\varXi \times \Upsilon$ is the mapping

  $$ 2^{\{\texttt {0} ,\texttt {1} \}^*} \!\!\ni O \mapsto \big ( \varXi (\{\vec v:\texttt {0} \vec v\in O\}), \Upsilon (\{\vec w:\texttt {1} \vec v\in O\})\big ) \in X\times Y.$$

• (e) Following up on Definition  1f), the second-order representation induced by a presented metric space $(X,d,\xi )$ is the mapping

  $$ \varXi :\subseteq \!2^{\{\texttt {0} ,\texttt {1} \}^*} \!\!\ni \big \{\langle {\text {bin}}(2^m),{\text {bin}}(2^j)\rangle : {\text {bin}}(a_m)_{_j}=\texttt {1} \big \} \mapsto x\in X $$

  for every $\xi$-name $\bar{a}=(a_m)_{_m}\in \mathbb {N}^\omega$ of x.

• (f) Fix presented metric spaces $(X,d,\xi )$ and $(Y,e,\upsilon )$ with induced (first-order) representations $\xi$ and $\upsilon$. Justified by Fact 2(c), equip (any fixed compact subset $\mathcal {Z}$ of) the space C(X, Y) of continuous total functions $f:X\rightarrow Y$ with the following second-order representation $\upsilon ^\xi$: Let

  $$\begin{aligned} O\;=\; \big \{ \langle {\text {bin}}(a),{\text {bin}}(2^m),{\text {bin}}(2^j)\rangle \,:\, a\in&{\text {dom}}(\xi ), \\&\big \langle {\text {bin}}\big (\varphi (a,m)\big )\big \rangle _j=\texttt {1} \big \} \;\subseteq \; \{\texttt {0} ,\texttt {1} \}^* \end{aligned}$$

  be an $\upsilon ^\xi$-name of $f\in C(X,Y)$ for every mapping $\varphi :{\text {dom}}(\xi )\times \mathbb {N}\subseteq \mathbb {N}\times \mathbb {N}\rightarrow {\text {dom}}(\upsilon )\subseteq \mathbb {N}$ where $\big (\varphi (a,m)\big )_{m}$ is an $\upsilon$-name of $f\big (\xi (a)\big )$.

So Item (c) is about functions with ordinary/first-order represented co-domain, (g) with second-order ones. And $\upsilon ^\xi$ according to Item (f) encodes (approximations in terms of the dense sequence in Y given by $\upsilon$ to) the values of f on the dense sequence in X given by $\xi$; cmp. [KaPa15, top of p. 8]. The fixed-depth stacks and subtle semantics of query tapes have been well justified in the discrete setting [Wils88, Buss88, ACN07] as well as in computational analysis [KaOt14]. Definition 8(f) does not (yet) incorporate quantitative information about continuity of f. In the case $\mathcal {Z}={\text {Lip}}_1([0;1],[0;1])$ the representation here called $\rho ^\rho$ is (equivalent to one) well-known [KaCo10, KORZ12, FHHP15, FeZi15]; and renders application $(f,x)\mapsto f(x)$ computable in polynomial-time.

7 Representing $L^p$ and Sobolev Spaces

Recall that, for compact $X\subseteq \mathbb {R}^d$, $L^p(X)=W^{0,p}(X)$ consists of all measurable (but not necessarily continuous) functions $f:X\rightarrow \mathbb {R}$ such that $\Vert f\Vert _p<\infty$; and, more generally, $W^{k,p}(X)$ of all f whose weak partial derivatives $\partial ^{\vec j}f:=\partial x_1^{j_1}\cdots \partial x_d^{j_d} f$ up to order $\Vert \vec j|:=j_1+\cdots +j_d\le k$ belong to $L^p(X)$, equipped with the norm $\Vert f\Vert _{k,p}:=\max _{|\vec j|\le k}\Vert \partial ^{\vec j} f\Vert _p$. By Lemma 5(c) and the extension of Theorem 6, no (first or) second-order representation of ${\text {Lip}}_1([0;1],[0;1])\subseteq L_p[0;1]$ can simultaneously render both $(f,g)\mapsto |f-g|$ and $f\mapsto \Vert f\Vert _p$ polynomial-time computable.

Definition 9

• (a) Inspired by Definition 1(h) call $\mu :\mathbb {N}\rightarrow \mathbb {N}$ an $L^p$-modulus of $f\in L^p[0;1]$ if $\root p \of {\int _0^1 |f(t+h)-f(t)|^p\,dt}<2^{-m}$ whenever $|h|<2^{-\mu (m)}$, with the convention $f(t)\equiv 0$ for $t\not \in [0;1]$.

• (b) Abbreviate $W^{k,p}_\mu [0;1] \;:=\; \big \{ f\in W^{k,p}[0;1]: \partial ^k f \text { has } L^p\text {-modulus }\mu \big \}$.

• (c) Let $\varXi$ denote the second-order representation of $L^1[0;1]\supseteq W^{k,p}[0;1]$ s.t. a $\varXi$-name of f is a $\rho ^\rho$-name of the continuous $[0;1]\ni s\mapsto \int _0^s f(t)\,dt\in \mathbb {R}$.

By Fréchet-Kolmogorov, $Y\subseteq L^p([0;1])$ is relatively compact iff there exists some $\mu$ with $Y\subseteq W^{0,p}_\mu [0;1]$: Our convention of extending f with zero asserts $W^{0,p}_\mu$ to be bounded by $2^{\mu (0)}$. Although harder than Lemma 5d), we can prove

Theorem 10

Fix polynomial-time computable $p\ge 1$ and strictly increasing $\mu$.

• (a) $\log \big \lfloor W^{0,p}_\mu \big ([0;1]\big ) \big \rfloor (n) \;=\;\mu \big (n\pm \varTheta (1)\big )$.

• (b) For any fixed polynomial $\mu$, the embedding $W_\mu ^{1,p}[0;1]\hookrightarrow C_{n\mapsto \mu (n+1)}[0;1]$ is well-defined and $(\varXi ,\rho ^\rho )$-computable in polynomial time.

• (c) For any fixed $k\in \mathbb {N}$ and polynomial $\mu$, differentiation $\partial :W_\mu ^{k+1,p}[0;1]\rightarrow W_\mu ^{k,p}[0;1]$ is well-defined and $(\varXi ,\varXi )$-computable in polynomial time.

• (d) For any fixed $k\in \mathbb {N}$ and polynomial $\mu$, the embedding $W_\mu ^{k+1,p}[0;1]\hookrightarrow W^{k,p}[0;1]$ is $(\varXi ,\varXi )$-computable in polynomial time.