Name
Title | ||
|---|---|---|
Computational benefit of smoothness: Parameterized bit-complexity of numerical operators on analytic functions and Gevrey’s hierarchy |
Abstract | ||
|---|---|---|
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/2n (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 (=C∞) 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. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1016/j.jco.2015.05.001 | Journal of Complexity |
Keywords | DocType | Volume |
Computational complexity,Rigorous numerics,Smoothness,Gevrey hierarchy | Journal | 31 |
Issue | ISSN | Citations |
5 | 0885-064X | 1 |
PageRank | References | Authors |
0.35 | 17 | 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 |