On in Polynomial Time Approximable Real Numbers and Analytic Functions
On in Polynomial Time Approximable Real Numbers and Analytic Functions
复制标题
论多项式时间内的近似实数和解析函数
DOI：
--
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
G. Hotz
中科院分区：
文献类型：
--
作者：
G. Hotz
复数的集合l Pol是一个域，它可以在多项式时间c·n k内近似，取决于精度2 −n。域的运算可以在<c · n 2的时间内近似，并且相对于以精度2 −n近似操作数1，2所需的时间更好。在加法和乘法的情况下，可以这样做：|ζ 1 |, |ζ 2 |其中c取决于a和多项式时间近似的运行时间中的常数，但在除法的情况下，常数还取决于|ζ | .这同样适用于多项式l Pol [x ]的环和有理函数f ∈ l Pol（x）的域。在多项式时间范围内的常数因子f（λ）的近似还取决于λ到f的奇点的距离。域l Pol是代数闭域。在多项式具有常系数的情况下，如果根是简单的并且根的隔离是预先计算的，则存在用牛顿法在线性时间内近似多项式的根的算法[Sch 82]。但这种预先计算需要很长时间[ESY 06]。最著名的算法来解决这个问题需要一个时间O（m5（τ +logm）2），m是多项式的次数和τ的二进制表示的系数的长度。在[Eig 08]、[ESY 06]中，基于比特流对非常系数问题进行了攻击。在[Eig 08]中可以找到一个很好的概述了最先进的。在这种情况下，系数不是固定常数，但由近似值给出的情况要复杂得多，因为预先计算取决于近似值的精度。很明显，在一般的近似根的多项式系数，这不能近似在一个时间O（n k），不能在这个时间。Ker-IKo在一元数表示的基础上讨论了逼近问题[Ko 91]。多项式时间算法相对于二元和一元表示显然是不一样的。本文的动机是多远的问题所提到的问题可以解决的全局多项式时间算法。这是一个运行时间<c·n k的算法，常数c仅取决于参数的多项式时间近似的常数和要计算的函数的域。我们证明了存在解析函数，这是可计算的所有有限域在这个意义上，这是真的解析函数可以表示为一个幂级数在z。
The set l Pol of complex numbers ζ , which can be approximated in a polynomial time cζ ·n k depending from the precision 2 −n , is a field. The operations of the field can be approximated in a time<c · n 2 and better relative to the time one needs to approximate the operands ζ 1 ,ζ 2 with precision 2 −n . In the case of addition and multiplication it can be done for |ζ 1 |, |ζ 2 |<a with a c depending from a and the constants in the running time of the polynomial time approximation of ζ 1,ζ 2, but in the case of division the constant depends additionally from |ζ | . The same holds for the ring of the polynomials l Pol [x ] and the field of the rational functions f ∈ l Pol (x ). The constant factor in the polynomial time bound of the approximation of f (ζ ) depend additionally from the distance of ζ from the singularities of f . The field l Pol is algebraically closed. In the case that the polynomials have constant coefficients there exist algorithms to approximate the roots of the polynomials in a linear time with the Newton method if the roots are simple and an isolation of the roots is precomputed [Sch82]. But this precomputation needs much time [ESY06]. The best known algorithms to solve this problem need a time O (m 5(τ +logm )2), m the degree of the polynomial and τ the length of the binary representation of the coefficients. The problem with not constant coefficients has been attacked on base of bitstreams in [Eig08], [ESY06]. In [Eig08] on can find an excellent overview of the state of art. In the case the coefficients are not fixed constants but given by approximations the situation is much more complicated because the precomputation depends from the precision of the approximation. It is clear that in general the approximation of a root of a polynomial with coefficients, which cannot be approximated in a time O (n k ), cannot be done in this time. Ker-I Ko discusses the approximation problems on base of the unary representation of the numbers [Ko91]. Polynomial time algorithms relative to dyadic and unary representation are obviously not the same. The motivation of this paper is the question how far the mentioned problems can be solved by global polynomial time algorithms. This are algorithms with a running time <c·n k with the constant c only depending from the constants of the polynomial time approximations of the arguments and the domain of the function to be computed. We prove that there exist analytic functions, which are computable on all finite domains in this sense and that analytic functions for which this is true can be represented by a power series in z.