Computational benefit of smoothness: Parameterized bit-complexity of numerical operators on analytic functions and Gevrey's hierarchy

摘要

The synthesis of (discrete) Complexity Theory with Recursive Analysis provides a quantitative algorithmic foundation to calculations over real numbers, sequences, and functions by approximation up to prescribable absolute error 1/2(n) (roughly corresponding to n binary digits after the radix point). In this sense Friedman and Ko have shown the seemingly simple operators of maximization and integration 'complete' for the standard complexity classes NP and #P - even when restricted to smooth (=e(infinity)) arguments. Analytic polynomial-time computable functions on the other hand are known to get mapped to polynomial-time computable functions: non-uniformly, that is, disregarding dependences other than on the output precision n.