IEICE TRANSACTIONS on Fundamentals
#P-hardness of Computing High Order Derivative and Its Logarithm
Summary :
In this paper, we show a connection between #P and computing the (real) value of the high order derivative at the origin. Consider, as a problem instance, an integer b and a sufficiently often differentiable function F(x) that is given as a string. Then we consider computing the value F(b)(0) of the b-th derivative of F(x) at the origin. By showing a polynomial as an example, we show that we have FP = #P if we can compute log 2F(b)(0) up to certain precision. The previous statement holds even if F(x) is limited to a function that is analytic at any x ∈ R. It implies the hardness of computing the b-th value of a number sequence from the closed form of its generating function.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E97-A No.6 pp.1382-1384
- Publication Date
- 2014/06/01
- Publicized
- Online ISSN
- 1745-1337
- DOI
- 10.1587/transfun.E97.A.1382
- Type of Manuscript
- Special Section LETTER (Special Section on Discrete Mathematics and Its Applications)
- Category
Authors
Ei ANDO
Sojo University
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Ei ANDO, "#P-hardness of Computing High Order Derivative and Its Logarithm" in IEICE TRANSACTIONS on Fundamentals,
vol. E97-A, no. 6, pp. 1382-1384, June 2014, doi: 10.1587/transfun.E97.A.1382.
Abstract: In this paper, we show a connection between #P and computing the (real) value of the high order derivative at the origin. Consider, as a problem instance, an integer b and a sufficiently often differentiable function F(x) that is given as a string. Then we consider computing the value F(b)(0) of the b-th derivative of F(x) at the origin. By showing a polynomial as an example, we show that we have FP = #P if we can compute log 2F(b)(0) up to certain precision. The previous statement holds even if F(x) is limited to a function that is analytic at any x ∈ R. It implies the hardness of computing the b-th value of a number sequence from the closed form of its generating function.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E97.A.1382/_p
Copy
@ARTICLE{e97-a_6_1382,
author={Ei ANDO, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={#P-hardness of Computing High Order Derivative and Its Logarithm},
year={2014},
volume={E97-A},
number={6},
pages={1382-1384},
abstract={In this paper, we show a connection between #P and computing the (real) value of the high order derivative at the origin. Consider, as a problem instance, an integer b and a sufficiently often differentiable function F(x) that is given as a string. Then we consider computing the value F(b)(0) of the b-th derivative of F(x) at the origin. By showing a polynomial as an example, we show that we have FP = #P if we can compute log 2F(b)(0) up to certain precision. The previous statement holds even if F(x) is limited to a function that is analytic at any x ∈ R. It implies the hardness of computing the b-th value of a number sequence from the closed form of its generating function.},
keywords={},
doi={10.1587/transfun.E97.A.1382},
ISSN={1745-1337},
month={June},}
Copy
TY - JOUR
TI - #P-hardness of Computing High Order Derivative and Its Logarithm
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1382
EP - 1384
AU - Ei ANDO
PY - 2014
DO - 10.1587/transfun.E97.A.1382
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E97-A
IS - 6
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - June 2014
AB - In this paper, we show a connection between #P and computing the (real) value of the high order derivative at the origin. Consider, as a problem instance, an integer b and a sufficiently often differentiable function F(x) that is given as a string. Then we consider computing the value F(b)(0) of the b-th derivative of F(x) at the origin. By showing a polynomial as an example, we show that we have FP = #P if we can compute log 2F(b)(0) up to certain precision. The previous statement holds even if F(x) is limited to a function that is analytic at any x ∈ R. It implies the hardness of computing the b-th value of a number sequence from the closed form of its generating function.
ER -
English
