论文标题
连续数据的定量编码和复杂性理论
Quantitative Coding and Complexity Theory of Continuous Data
论文作者
论文摘要
指定计算问题需要修复输入和输出的编码：将图形编码为邻接矩阵，字符作为整数，整数作为位字符串作为位字符串，反之亦然。对于此类离散数据，实际的编码通常是直接和/或复杂性的，从本质上讲（最多为多项式时间）；但是，关于连续数据，已经是实际数字自然表明具有非常不同属性的各种编码（所谓的表示），范围从通过定性通过定性且在多种方面和线性上的“合理”“合理”签名数字扩展的“不合理”二进制扩展等方面。但是，如何区分微积分和数字中常见的其他空间（例如sobolev）的其他空间的编码？ 关于定性的可计算性，Kreitz和Weihrauch（1985）已将可接受性确定为在无限二进制序列的cantor空间中表示的至关重要的标准是“合理的”。 CMP。 [doi：10.1007/11780342_48]。优化对度量空间的拓扑结构对复杂性的可计算性，我们将多项式/线性可接受性的理论发展为定性可接受性的两种定量改进。 我们还将定量的可接受性重新为代表性的定量连续性及其集合倒数，后者从[doi：10.4115/jla.2013.5.7]中采用了一种新的“顺序”连续性概念。通过建立一个定量的连续选择定理，用于紧凑的超级空间之间的多种功能，我们可以将上述定量主定理从函数扩展到多功能问题，也可以将搜索问题扩展。通过将Cantor（和Baire）的地面空间概括为其他（紧凑的）溃疡空间来捕获更高的复杂性。
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 (so-called REPRESENTATIONS) with very different properties, ranging from the computably 'unreasonable' binary expansion via qualitatively to polynomially and even linearly complexity-theoretically 'reasonable' signed-digit expansion. But how to distinguish between un/suitable encodings of other spaces common in Calculus and Numerics, such as Sobolev? With respect to qualitative computability, Kreitz and Weihrauch (1985) had identified ADMISSIBILITY as crucial criterion for a representation over the Cantor space of infinite binary sequences to be 'reasonable'; cmp. [doi:10.1007/11780342_48]. Refining computability over topological to complexity over metric spaces, we develop the theory of POLYNOMIAL/LINEAR ADMISSIBILITY as two quantitative refinements of qualitative admissibility. We also rephrase quantitative admissibility as quantitative continuity of both the representation and of its set-valued inverse, the latter adopting from [doi:10.4115/jla.2013.5.7] a new notion of 'sequential' continuity for multifunctions. By establishing a quantitative continuous selection theorem for multifunctions between compact ultrametric spaces, we can extend our above quantitative MAIN THEOREM from functions to multifunctions aka search problems. Higher-type complexity is captured by generalizing Cantor's (and Baire's) ground space for encodings to other (compact) ULRAmetric spaces.
