Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Let $f$ be an analytic function, and suppose that we want to compute $f(x)$. The input consists of the digits of $x$ and the output of a rational number approximating $f(x)$. A function $f$ is called easy if there is an algorithm which computes $f(x)$ with accuracy $2^{-n}$ using $n^{1+o(1)}$ arithmetic operations.

It is known that elementary functions like $e^x,\log x$ are easy.

Is it known (proven) about any reasonable function that it is hard (not easy)?

For an algorithm, using the AGM, showing that $e^x$ is easy, a reference is D. Newman, Rational approximation versus fast computer methods, Lectures on approximation and value distribution, pp. 149.174, Sém. Math. Sup., 79, Presses Univ. Montréal, Montreal, Que., 1982.

EDIT1: The same paper contains a proof that multiplication is easy (fast multiplication), and if $f$ is easy then the inverse function is easy (Newton's method).

EDIT2: I understand that with our present knowledge we cannot compute Euler's constant efficiently. But I don't know a proof that this is impossible.

share|improve this question
1  
My vague suspect is that many "reasonable" functions may be hard, but only "unreasonable" ones allow you to prove it (on that point being curiously reasonable) –  Pietro Majer Dec 16 '12 at 18:02
1  
I guess you actually mean digit operations, otherwise the parameter $n$ doesn't make sense. In that case, the representation is a serious issue and using digits is usually not the best; interval representation is generally much better (e.g., mathoverflow.net/questions/13166/… ). –  François G. Dorais Dec 16 '12 at 20:28
2  
Decimal digit representation is wrong, as it makes multiplication by 3 non-computable. –  Andrej Bauer Dec 17 '12 at 4:32
1  
Regarding the second edit: it is not even proved that Euler's constant is not rational, which (except I confused something) would seem like inevitable to establish any hardness of computation. –  quid Dec 17 '12 at 7:51
1  
The problem that stumped Feynman was: $\tan 10^{100}$. He had claimed that he could, in under 60 seconds, estimate the solution to any numerical problem that could be stated in 10 seconds, within 10 percent accuracy. –  S. Carnahan Dec 18 '12 at 16:05
show 12 more comments

3 Answers 3

Any (uniformly) polynomial-time computable function must have a polynomial modulus of (uniform) continuity [Ker-I Ko 1991,Theorem 2.10]. The function $0\lt x\mapsto1/\ln(e/x)$ is well-defined on [0;1] and (exponential-time) computable yet has no polynomial modulus of continuity at 0; see Example 1.12 in arXiv:1211.4974. It is not analytic at 0, though...

For the stronger question on 'simple' real numbers (i.e. constant functions, cmp. Norbert Müller's answer) that are not computable within polynomial space, say, confer periods in Model Theory and this article by Tent and Ziegler.

share|improve this answer
    
What is [Ko91]? –  Alexandre Eremenko Dec 17 '12 at 1:45
    
It is the book I cited in my answer. –  Andrej Bauer Dec 17 '12 at 4:30
    
Martin, let me try to clarify your statement that the function is not analytic. Log IS an easy function, in the sense that it can be computed with $n^{1+o(1)}$ operations for every $x$. The $o(1)$ may depend on $x$. The theorem you cite is about polynomial time uniform in $x$. –  Alexandre Eremenko Dec 17 '12 at 6:33
5  
The point, I think, is that $f(0) = 0$ while $f(e^{-n})= 1/(n+1)$; to get $f(x)$ accurate to within $e^{-k}$ you need to be able to tell the difference between $x=0$ and $x=\exp(e^{-k})$, which requires looking at exponentially many digits of $x$. Of course $f(x)$ is not analytic at $x=0$. Any function that is Lipschitz on a compact set has a polynomial modulus of continuity. –  Robert Israel Dec 17 '12 at 6:55
    
Thank you for this very nice example! –  François G. Dorais Dec 17 '12 at 10:00
add comment

If we consider constant functions (trivially analytic...), then we could change the original question to: Are there "reasonable" real numbers that are not computable in quadratic time? As there is a time hierachy theorem on the real numbers (Norbert Th. Müller: Subpolynomial Complexity Classes of Real Functions and Real Numbers. ICALP 1986: 284-293), there exist numbers in qubic time that are not in quadratic time. Whether there numbers are as "reasonable" as $\pi$ or $e$, however, is another question...

share|improve this answer
add comment

Here are a couple of relevant references. I will try to find one that is specifically about the exponential functions. But in general it is a bit too optimistic to hope for such low complexity as $n^{1 + o(1)}$. You cannot expect it to be faster than multiplication.

share|improve this answer
    
$\Omega(M(n))$ is a trivial lower bound, where $M(n)$ is complexity of multiplication. I think the OP might be searching for the $O(n^{1+o(1)}M(n)$?? –  Suvrit Dec 16 '12 at 20:21
    
But multiplication of $n$-digit integers is $n^{1+o(1)}$ using Schönhage–Strassen and similar algorithms. –  Robert Israel Dec 16 '12 at 20:25
    
Ah, I see. Thanks for the clarification Robert. –  Suvrit Dec 16 '12 at 20:33
    
I don't disagree with your lack of optimism. However, multiplication is $n^{1+o(1)}$ via FFT. It sounds like you're saying otherwise, but I think it's just a minor error in the way you formulated your statement. Anyway, it's still too optimistic to think that everything can be almost as fast as multiplication. –  François G. Dorais Dec 16 '12 at 20:36
    
Andrej, I did NOT ask anything about the exponential function. –  Alexandre Eremenko Dec 16 '12 at 21:38
show 3 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.