Computational benefit of smoothness: Parameterized bit-complexity of numerical operators on analytic functions and Gevrey's hierarchy
Computational benefit of smoothness: Parameterized bit-complexity of numerical operators on analytic functions and Gevrey's hierarchy
复制标题
平滑度的计算优势：解析函数和 Gevrey 层次结构上数值运算符的参数化位复杂度
DOI：
10.1016/j.jco.2015.05.001
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
M. Ziegler
中科院分区：
文献类型：
--
作者：
A. Kawamura;N. Müller;C. Rösnick;M. Ziegler
（离散）复杂性理论与递归分析的综合为实数、序列和函数的计算提供了定量算法基础，近似可指定的绝对误差 1/2 n（大致对应于小数点后的 n 个二进制数字）。从这个意义上说，Friedman 和 Ko 已经展示了对于标准复杂性类 NP 和# P 而言，看似简单的最大化和积分“完整”运算符，即使仅限于平滑 (= C∞) 参数。另一方面，众所周知，解析多项式时间可计算函数会映射到多项式时间可计算函数：非均匀地，即忽略除输出精度 n 之外的依赖性。目前的工作研究了平滑函数子类上自然算子 Λ 的统一参数化复杂性：求值、逐点加法和乘法、（迭代）微分、积分和最大化。我们确定自然整数参数 k= k (f)，当作为函数参数 f 的近似值的丰富给出时，允许可计算地生成 Λ (f) 的近似值；我们根据输出精度 n 和 k 来探索此类计算足够且必要的渐近最坏情况运行时间。事实证明，莫里斯·格弗里 (Maurice Gevrey) 1918 年从解析函数到（正下方）平滑函数的经典层次结构提供了对最大化和积分的统一计算复杂性的定量衡量，它非均匀地展示了从易处理（即多项式时间）到难处理（在 NP“硬度”意义上）的相变。我们的证明方法涉及硬分析、近似理论以及基于信息的复杂性对位模型的适应。
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 (= 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. The present work investigates the uniform parameterized complexity of natural operators Λ on subclasses of smooth functions: evaluation, pointwise addition and multiplication,(iterated) differentiation, integration, and maximization. We identify natural integer parameters k= k (f) which, when given as enrichment to approximations to the function argument f, permit to computably produce approximations to Λ (f); and we explore the asymptotic worst-case running time sufficient and necessary for such computations in terms of the output precision n and said k. It turns out that Maurice Gevrey’s 1918 classical hierarchy climbing from analytic to (just below) smooth functions provides for a quantitative gauge of the uniform computational complexity of maximization and integration that, non-uniformly, exhibits the phase transition from tractable (ie polynomial-time) to intractable (in the sense of NP-‘hardness’). Our proof methods involve Hard Analysis, Approximation Theory, and an adaptation of Information-Based Complexity to the bit model.
登录
查看更多内容
DOI：
10.1007/978-3-642-38896-5
发表时间：
2013-08
期刊：
--
影响因子：
--
作者：
Peter Bürgisser;F. Cucker
通讯作者：
Peter Bürgisser;F. Cucker
为什么基于信息的复杂性使用实数模型？
DOI：
10.1016/s0304-3975(98)00300-4
发表时间：
1999
期刊：
Theor. Comput. Sci.
影响因子：
--
作者：
H. Wozniakowski
通讯作者：
H. Wozniakowski
求解无界域上多项式时间内的解析微分方程
DOI：
--
发表时间：
2011
期刊：
International Symposium on Mathematical Foundations of Computer Science
影响因子：
--
作者：
Olivier Bournez;D. Graça;Amaury Pouly
通讯作者：
Amaury Pouly
解析机的表示定理和解析函数的可计算性
影响因子：
0.5
作者：
Tobias Gärtner;G. Hotz
通讯作者：
G. Hotz
论多项式时间内的近似实数和解析函数
DOI：
--
发表时间：
2009
期刊：
影响因子：
--
作者：
G. Hotz
通讯作者：
G. Hotz