التفاصيل البيبلوغرافية
| العنوان: |
Quantitative Coding and Complexity Theory of Continuous Data: Part I: Motivation, Definition, Consequences. |
| المؤلفون: |
Lim, Donghyun1 (AUTHOR) klimdhn@kaist.ac.kr, Ziegler, Martin1 (AUTHOR) ziegler@kaist.ac.kr |
| المصدر: |
Journal of the ACM. Feb2025, Vol. 72 Issue 1, p1-39. 39p. |
| مصطلحات موضوعية: |
COMPUTABLE analysis, GENERALIZED spaces, COMPACT spaces (Topology), REAL numbers, CODING theory, METRIC spaces |
| مستخلص: |
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 "unreasonable", 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 ultrametric 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. [ABSTRACT FROM AUTHOR] |
|
Copyright of Journal of the ACM is the property of Association for Computing Machinery and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) |
| قاعدة البيانات: |
Business Source Index |