key: cord-0046131-gotvzg2u
authors: Lim, Donghyun; Ziegler, Martin
title: Quantitative Coding and Complexity Theory of Compact Metric Spaces
date: 2020-06-24
journal: Beyond the Horizon of Computability
DOI: 10.1007/978-3-030-51466-2_18
sha: c0048d9f009830e92ecd4ffade883655e77980b2
doc_id: 46131
cord_uid: gotvzg2u

Specifying a computational problem requires fixing encodings for input and output: encoding graphs as adjacency matrices, characters as integers, integers as bit strings, and vice versa. For such discrete data, the actual encoding is usually straightforward and/or complexity-theoretically inessential (up to polynomial time, say); but concerning continuous data, already real numbers naturally suggest various encodings with very different computational properties. With respect to qualitative computability, Kreitz and Weihrauch (1985) had identified admissibility as crucial property for “reasonable” encodings over the Cantor space of infinite binary sequences, so-called representations. For (precisely) these does the Kreitz-Weihrauch representation (aka Main) Theorem apply, characterizing continuity of functions in terms of continuous realizers. We similarly identify refined criteria for representations suitable for quantitative complexity investigations. Higher type complexity is captured by replacing Cantor’s as ground space with more general compact metric spaces, similar to equilogical spaces in computability.

Machine models formalize computation: they specify means of input, operations, and output of elements from some fixed set Γ ; as well as measures of cost and of input/output 'size'; such that Complexity Theory can investigate the dependence of the former on the latter. Problems over spaces X other than Γ are treated by encoding its elements/instances over Γ .

Example 1. a) Recall the Turing machine model operating on the set Γ of finite (e.g. decimal or binary) sequences, and consider the space X of graphs: encoded for example as adjacency matrices' binary entries. Operations amount to local transformations of, and in local dependence of, the tape contents. Size here is an integer: n commonly denotes the number of nodes of the graph, or the binary length of the encoded matrix, both polynomially related to each other. b) Consider the space X = N of natural numbers, either encoded in binary or in unary: their lengths are computably but not polynomially related, and induce computably equivalent but significantly different notions of computational complexity. c) Recall the type-2 machine model [Wei00, §2.1] operating on the Cantor space C := {0, 1} N of infinite binary sequences; and the real unit interval X = [0; 1], equipped with various so-called representations [Wei00, §4.1]: surjective partial mappings from C onto X that formalize (sequences of) approximations up to any given absolute error bound 1/2 n , n ∈ N. In the sequel we will focus on the part of the question concerned with encoding continuous data. Section 2 recalls classical criteria and notions: qualitative admissibility of computably 'reasonable' representations for the Kreitz-Weihrauch Main Theorem (Subsect. 2.1), and complexity parameters for a quantitative Main Theorem in the real case (Subsect. 2.2). Section 4 combines both towards generic quantitative admissibility and an intrinsic complexity-theoretic Main Theorem. The key is to consider metric properties of the inverse of a representation, which is inherently multivalued a 'function'. To this end Sect. 3 adopts from [PZ13] a notion of quantitative (uniform) continuity multifunctions (Subsect. 3.1) and establishes important properties (Subsect. 3.2), including closure under a generalized conception of restriction. We close with applications to higher-type complexity.

Common models of computation naturally operate on some particular domain Γ (e.g., in/finite binary sequences, string functions, etc.); processing data from another domain X (graphs, real numbers, continuous functions) requires agreeing on some way of encoding (the elements x of) X over Γ .

Formally, a representation is a surjective partial mapping ξ :⊆ Γ X; any γ ∈ dom(ξ) is called a name of x = ξ(γ) ∈ X; and for another representation υ of Y , computing a total function f : X → Y means to compute some (ξ, υ)-realizer :

Some representations are computably 'unsuitable' [Tur37] , including the binary expansion 

Already for the case X = [0; 1] of real numbers, it thus takes particular care to arrive at a complexity-theoretically 'reasonable' representation [Wei00, Theorem 7.3.1]; and even more so for continuous real functions [KC12] , not to mention for more involved spaces [Ste17] .

Regarding computability on a large class of topological spaces X, an important criterion for a representation is admissibility [KW85, Sch02] : 

In particular discontinuous functions are incomputable.

The search for quantitative versions of admissibility and the Main Theorem is guided by above notion of qualitative admissibility. It revolves around quantitative metric versions of qualitative topological properties, such as continuity and compactness, obtained via Skolemization. Further guidance comes from reviewing the real case.

Recall that a modulus of continuity of a function f : X → Y between compact metric spaces (X, d) and (Y, e) is a strictly increasing mapping μ :

In this case one says that f is μ-continuous. Actually we shall occasionally slightly weaken this notion and require Condition (1) only for all sufficiently large n. In 

Multifunctions are unavoidable in real computation [Luc77] . Their introduction simplifies several considerations; for example, every function f : X → Y has a (possibly multivalued) inverse f −1 : Y ⇒ X. Formally, a partial multivalued function (multifunction) F between sets X, Y is a relation F ⊆ X × Y that models a computational search problem: Given (any name of) x ∈ X, return some (name of some) y ∈ Y with (x, y) ∈ F . One may identify the relation f with the single-valued total function F : X x → {y ∈ Y | (x, y) ∈ F } from X to the powerset 2 Y ; but we prefer the notation f :⊆ X ⇒ Y to emphasize that not every y ∈ F (x) needs to occur as output. Letting the answer y depend on the code of x means dropping the requirement for ordinary functions to be extensional; hence, in spite of the oxymoron, such F is also called a non-extensional function. Note that no output is feasible in case F (x) = ∅. 

Note that every (single-valued) function is pointwise compact. A computational problem, considered as total single-valued function f : X → Y , becomes 'easier' when restricting arguments to x ∈ X ⊆ X, that is, when proceeding to f = f | X for some X ⊆ X. A search problem, considered as total multifunction F : X ⇒ Y , additionally becomes 'easier' when proceeding to any F ⊆ X ⇒ Y satisfying the following: F (x) ⊇ F (x) for every x ∈ dom(F ). We call such F also a restriction of F , and write F F . A single-valued function f : 

For representations ξ of X and υ of Y , the following are equivalent:

Every restriction f of a single-valued continuous function f is again continuous. This is not true for multifunctions with respect to hemi continuity. Instead Definition 12 below adapts, and quantitatively refines, a notion of continuity for multifunctions from [PZ13] such as to satisfy the following properties:

continuous. e) For every ε > 0, the soft Heaviside 'function' h ε is id-continuous, but not for ε = 0:

Our notion of quantitative (uniform) continuity is inspired by [BH94] and [PZ13,

Definition 12. Fix metric spaces (X, d) and (Y, e) and strictly increasing μ : N → N. A total multifunction F : X ⇒ Y is called μ-continuous if there exists some n 0 ∈ N, and to every x 0 ∈ X there exists some y 0 ∈ F (x 0 ), such that the following holds for every k ∈ N:

The parameter n 0 is introduced for the purpose of Proposition 11d+e). Recall that also in the single-valued case we sometimes understand Eq.

(1) to hold only for all n ≥ n 0 . A continuous multifunction on Cantor space, unlike one for example on the reals [PZ13, Fig. 5 ], does admit a continuous selection, and even a bound on the modulus: Theorem 13. Suppose (Y, e) is compact of diameter diam(Y ) ≤ 1 and satisfies the strong triangle inequality e(x, z) ≤ max e(x, y), e(y, z) ≤ e(x, y) + e(y, z).

(2)

If G :⊆ C ⇒ Y is μ-continuous and pointwise compact with compact domain dom(G) ⊆ C, then G admits a μ n + O(1) -continuous selection.

Generalizing both Fact 5 and Theorem 7, Lemma 10 and Proposition 11 and Theorem 13 together in fact yields the following quantitative counterpart to the qualitative Main Theorem for generic compact metric spaces: 

According to Theorem 14, quantitative continuity of a (multi)function g is connected to that of a (single-valued) realizer G, subject to properties of the representations ξ, υ under consideration. A 'true' quantitative Main Theorem should replace these extrinsic parameters with ones intrinsic to the co/domains X, Y : by imposing suitable conditions on the representations as quantitative variant of qualitative admissibility [Lim19] .

Definition 15. The entropy of a compact metric space (X, d) is the mapping η = η X : N → N such that X can be covered by 2 η(n) closed balls B n (x) of radius 2 −n , but not by 2 η(n)−1 .

Introduced by Kolmogorov [KT59] , η thus quantitatively captures total boundedness [Koh08, Definition 18.52]. Its connections to computational complexity are well-known [Wei03, KSZ16] . is compact when equipped with the supremum norm and has entropy η(n) = Θ(2 n ). c) More generally fix a connected compact metric space (X, d) of diameter diam(X) := sup{(d(x, x ) :

x, x ∈ X} with entropy η. Then the space X of non-expansive functional s Λ : X → [0; 1] is compact when equipped with the supremum norm and has entropy η (n) = 2 η(n±O(1)) .

Items (b) and (c) are relevant for higher-type complexity theory.

Since computational efficiency is connected to quantitative continuity (Subsect. 2.2), in Theorem 14 one prefers ξ and ξ −1 with 'small' moduli; similarly for υ and υ −1 . A simple but important constraint has been identified in [Ste16, Lemma 3.1.13]-originally for single-valued functions, but its proof immediately extends to multifunctions.

Lemma 17. If surjective (multi)function g : X ⇒ Y is μ-continuous, then it holds η Y (n) ≤ η X • μ(n) (for all sufficiently large n).

This suggests the following tentative definition:

Definition 18. Fix some compact metric space Γ , and recall Example 1g). a) A representation of compact metric space (X, d) is a continuous partial surjective (single-valued) mapping ξ :⊆ Γ X. b) Fix another compact metric space Δ and representation υ :⊆ Δ Y . A (ξ, υ)-realizer of a total (multi)function f : X ⇒ Y is a (single-valued) function F : dom(ξ) → dom(υ) satisfying any/all conditions of Lemma 10d). c) Representation ξ :⊆ Γ X is polynomially admissible if (i) It has a modulus of continuity μ such that η Γ • μ is bounded by a (first or second order) polynomial in the precision parameter n and in the entropy η of X. (ii) Its multivalued inverse ξ −1 has polynomial modulus of continuity μ . d) Call total (multi)function f : X ⇒ Y polynomial-time computable iff it can be computed in time bounded by a (first or second order) polynomial in the output precision parameter n and in the entropy η of X.

In view of Lemma 10c+d) we deliberately consider only single-valued representations [Wei05] . Item d) includes Definition 8 as well as higher types, such as Example 16b) and c). Note that Item (c i) indeed quantitatively strengthens Definition 4i). And Item (c ii) quantitatively strengthens Definition 4ii): For νcontinuous ζ, Theorem 13 yields a ν • μ -continuous selection G of ξ −1 • ζ, that is, with ζ = ξ • G according to Lemma 10.

Equilogical spaces

Continuity and computability of relations

A new characterization of type-2 feasibility

Complexity theory for operators in analysis

Complexity Theory of Real Functions

Applied Proof Theory

Polynomial running times for polynomial-time oracle machines

Type-two polynomial-time and restricted lookahead

Complexity theory of (functions on) compact metric spaces

E-entropy and E-capacity of sets infunctional spaces. Uspekhi Mat

Theory of representations

Representations of totally bounded metric spaces and their computational complexity

A fundamental effect in computations on real numbers. Theoret

Polynomial and abstract subrecursive classes

Parametrised second-order complexity theory with applications to the study of interval computation

Relative computability and uniform continuity of relations

Effectivity in spaces with admissible multi representations

Spaces allowing type-2 complexity theory revisited

Computational complexity theory for advanced function spaces in analysis

Complexity theory for spaces of integrable functions

On computable numbers, with an application to the "Entscheidungsproblem

Computable Analysis

Computational complexity on computable metric spaces

Multi-functions on multi-represented sets are closed under flowchart programming