Quantitative Coding and Complexity Theory of <i>Continuous</i> Data: Part I: Motivation, Definition, Consequences

When encoding real numbers as (necessarily infinite) bit-strings, the naïve binary/decimal expansion is well-known [ doi:10.1112/plms/s2-43.6.544 ] computably “ un reasonable”, rendering, for example, tripling qualitatively discontinuous on Cantor’s sequence space. Encoding reals as sequences of (finite integer numerators and denominators, in binary, of) rational approximations does make common operations qualitatively computable, yet admits no bounds on their computational complexity/quantitative continuity. Dyadic approximations, on the other hand, are known polynomially, and signed binary expansions even linearly, “reasonable” in a rigorous sense recalled in the introduction of this work. But how to distinguish between un/suitable encodings of spaces common in Calculus beyond the reals, such as Banach or Sobolev? With respect to qualitative computability/continuity on topological spaces, the technical condition of admissibility had been identified [ doi:10.1016/0304-3975(85)90208-7 ] for an encoding over Cantor space (historically called a representation ) to be “reasonable” [ doi:10.1007/978-3-030-59234-9_9 ] . Roughly speaking, admissibility requires the representation to be (i) continuous, and to be (ii) maximal with respect to continuous reduction. Admissible representations exist for a large class of spaces. And for (precisely) these does the Kreitz–Weihrauch—sometimes aka Main —Theorem of Computable Analysis hold, which characterizes continuity of functions by continuity of mappings translating codes, so-called realizers . We refine qualitative computability/continuity on topological spaces to quantitative continuity/complexity on metric spaces by proposing a notion, and investigating the properties, of polynomially/linearly admissible representations. Roughly speaking, these are (i) close to “optimally” continuous, namely linearly/polynomially relative to the space’s entropy, and they are (ii) maximal with respect to relative linear/polynomial quantitatively continuous reductions defined in the main text. Quantitatively admissible representations are closed under composition over generalized ground spaces beyond Cantor’s. Such representations exhibit a quantitative strengthening of the qualitative Main Theorem , namely now characterizing quantitative continuity of functions by quantitative continuity of realizers. A large class of compact metric spaces is shown to admit polynomially admissible representations over compact ultra metric spaces, and some even a generalization of the linearly admissible signed binary encoding. Quantitative admissibility thus provides the desired criterion for complexity-theoretically “reasonable” encodings.