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

递归分析是由艾伦·图灵提出的，作为真实的数的可计算性理论，在有理逼近的意义上，直到可规定的绝对误差1/2 ^N，更一般地，在任何连续基数的宇宙上，关于其元素作为无限二进制序列在类型2机器上的固定编码（cmp. Weihrauch 2000）。这种观点补充了通常与固定精度（比如双倍）的“大”输入维度（例如矩阵维度）有关的常见数字，并使用MPFR，GMP或iRRAM等库捕获自适应精度的算法。单价测试变得不连续，因此在这样的设置中不可计算（“主要定理”），因此需要诉诸多值（即内涵）函数。自80年代和90年代以来，已经开发了纯粹可计算性的复杂性理论改进，例如，作者：H.Friedman，K. I.Ko和N.T.Müller，（单值）真实的函数以及最大值、积分和常微分方程解等运算符：在不均匀的意义上，例如，已知多项式时间可计算解析函数具有多项式时间可计算积分，但不知道如何获得该积分，以及从什么数据获得该积分，以及该积分的实际运行时间是多少实际上，Akitoshi Kawamura和Stephen A. Cook（2010）在所谓的二阶多项式方面，cmp。Mehlhorn（1976）和Kapron&Cook（1996）提出的结构复杂性理论，我们将这种结构复杂性理论分层为定量复杂性理论，并将其推广到多值函数和算子。更精确地说，我们分析已知的，并开发新的，算法的多项式（在规定的输出精度N）的指数运行时间和它的依赖参数的（功能）空间正在考虑。这将允许对它们的实际效率进行更现实的估计，并加强与区间计算/验证数值的实践的联系。补充较低的复杂性界限往往出现在考虑中的函数和算子的（多值）连续性模的定量分析-及其多值推广（Pauly&齐格勒2011）。为了获得这样的估计，我们适应对手的方法从基于信息的复杂性（IBC，密切相关的Blum-Shub-Smale模型）的递归分析的设置，其中函数评估涉及近似输出和输入，即提供非本地信息。

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.