Name
Title | ||
|---|---|---|
Parameterized Uniform Complexity in Numerics: from Smooth to Analytic, from NP-hard to Polytime |
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. |
Year | Venue | Field |
|---|---|---|
2012 | CoRR | Complexity class,Discrete mathematics,Mathematical optimization,Structural complexity theory,Parameterized complexity,Analytic function,Descriptive complexity theory,Gap theorem,Mathematics,Fast-growing hierarchy,Computable function |
DocType | Volume | Citations |
Journal | abs/1211.4974 | 6 |
PageRank | References | Authors |
0.61 | 1 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Akitoshi Kawamura | 1 | 102 | 15.84 |
| Norbert Th. Müller | 2 | 71 | 12.11 |
| Carsten Rösnick | 3 | 14 | 1.98 |
| Martin Ziegler | 4 | 7 | 3.33 |