Parameterized Uniform Complexity in Numerics: from Smooth to Analytic, from NP-hard to Polytime
From MaRDI portal
Publication:6237362
arXiv1211.4974MaRDI QIDQ6237362FDOQ6237362
Authors: Akitoshi Kawamura, Norbert Th. Müller, Carsten Rösnick, Martin Ziegler 
Publication date: 21 November 2012
Abstract: The synthesis of classical Computational Complexity Theory with Recursive Analysis provides a quantitative foundation to reliable numerics. Here the operators of maximization, integration, and solving ordinary differential equations are known to map (even high-order differentiable) polynomial-time computable functions to instances which are `hard' for classical complexity classes NP, #P, and CH; but, restricted to analytic functions, map polynomial-time computable ones to polynomial-time computable ones -- non-uniformly! We investigate the uniform parameterized complexity of the above operators in the setting of Weihrauch's TTE and its second-order extension due to Kawamura&Cook (2010). That is, we explore which (both continuous and discrete, first and second order) information and parameters on some given f is sufficient to obtain similar data on Max(f) and int(f); and within what running time, in terms of these parameters and the guaranteed output precision 2^(-n). It turns out that Gevrey's hierarchy of functions climbing from analytic to smooth corresponds to the computational complexity of maximization growing from polytime to NP-hard. Proof techniques involve mainly the Theory of (discrete) Computation, Hard Analysis, and Information-Based Complexity.
Complexity and performance of numerical algorithms (65Y20) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
This page was built for publication: Parameterized Uniform Complexity in Numerics: from Smooth to Analytic, from NP-hard to Polytime
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6237362)
