Quantitative Uniform Complexity Theory of Multivalued Real Functions and Operators in Analysis

递归分析是由艾伦·图灵发起的，它是关于实数的可计算性理论，在有理逼近的意义上，直到可规定的绝对误差1/2^N，更一般地，关于其元素在类型2机器上的无限二进制序列的固定编码，在任何连续统基数宇宙上(CMP)。威拉赫2000年)。该视图补充了通常关注固定精度(比方说双精度)的“大”输入维度(例如矩阵维度)的常见数值，并使用MPFR、GMP或IRRAM等库捕获自适应精度的算法。自80年代和90年代以来，由H.Friedman、K.-I.Ko和N.T.Müler为(单值)实函数和像最大值、积分和常微分方程式的解这样的算子发展了仅可计算性的复杂性理论精化：例如，在非一致意义上，多项式时间可计算解析函数已知具有多项式时间可计算积分，但不知道如何获得它，以及从什么数据及其运行时间实际是什么(不是多项式)或依赖于什么。事实上，Akitoshi Kawamura和Stephen A.Cook(2010)在所谓的二阶多项式的概念下，找到了算子的有效一致可计算性的一个合理的概念。Mehlhorn(1976)和Kapron&Cook(1996)。我们将这种结构分层为一种数量复杂性理论，并将其推广到多值函数和算子。更确切地说，我们分析了已知的算法，并开发了关于它们的多项式的指数(在规定的输出精度N中)运行时间及其对所考虑的(函数)空间的参数的依赖的新算法。这将使人们能够更切合实际地估计它们的实际效率，并加强与区间计算/验证数值实践的联系。对所考虑的函数和运算符的(多值)连续性的模及其多值推广的定量分析通常会补充较低的复杂性界限(Paly&Ziegler 2011)。为了获得这样的估计，我们采用了敌对方法，从基于信息的复杂性(IBC，与Blum-Shub-Smer模型密切相关)到递归分析的设置，其中函数评估涉及近似输出和输入，即提供非局部信息。

Recursive Analysis was initiated by Alan Turing as the theory of computability over real numbers in the sense of rational approximations up to prescribable absolute error 1/2^N and, more generally, over any universe of continuum cardinality with respect to a fixed encoding of its elements as infinite binary sequences on type-2 machines (cmp. Weihrauch 2000). This view complements common numerics which typically is concerned with 'large' input dimensions (e.g. the matrix dimension) of fixed precision (double, say), and captures arithmetic of adaptive accuracy using libraries like MPFR, GMP, or iRRAM. Univalent tests become discontinuous and thus uncomputable in thus setting ('Main Theorem') hence requires resorting to multivalued (i.e. intensional) functions.Complexity-theoretic refinements of mere computability have been developed since the 80ies and 90ies, e.g., by H.Friedman, K.-I.Ko, and N.T.Müller for (single-valued) real functions and for operators likemaximum, integral, and the solution to ordinary differential equations: in the nonuniform sense that, for instance, a polynomial-time computable analytic function is known to have a polynomial-time computable integral but not how to obtain that and from what data and what its running time actually is (other than polynomial) or depends on. As matter of fact a reasonable notion of efficient uniform computability of operators was found by Akitoshi Kawamura and Stephen A. Cook (2010) in terms of so-called second-order polynomials, cmp. Mehlhorn (1976) and Kapron&Cook (1996).We stratify this structural into a quantitative complexity theory and extend it to multivalued functions and operators. More precisely we analyze known, and develop new, algorithms with respect to the exponent of their polynomial (in the prescribed output precision N) running time and its dependence on parameters of the (function) space under consideration. This will allow for a more realistic estimate of their practical efficiency and strengthen the connections to the practice of interval computation / validated numerics. Complementing lower complexity bounds often emerge from quantitative analysis of the modulus of (multivalued) continuity of the functions and operators under consideration --- and its multivalued generalization (Pauly&Ziegler 2011). To obtain such estimates we adapt adversary methods from Information-Based Complexity (IBC, closely related to the Blum-Shub-Smale model) to the setting of Recursive Analysis where function evaluation involves both approximate output and input, i.e. provides non-local information.