21
$\begingroup$

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.

Remark. I am mostly interested in analytic functions, even "special functions". Are they all easy?

Improve this question
$\endgroup$
17
  • 1
    $\begingroup$ 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) $\endgroup$
    – Pietro Majer
    Commented Dec 16, 2012 at 18:02
  • 1
    $\begingroup$ 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/… ). $\endgroup$
    – François G. Dorais
    Commented Dec 16, 2012 at 20:28
  • 2
    $\begingroup$ Decimal digit representation is wrong, as it makes multiplication by 3 non-computable. $\endgroup$
    – Andrej Bauer
    Commented Dec 17, 2012 at 4:32
  • 1
    $\begingroup$ 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. $\endgroup$
    – user9072
    Commented Dec 17, 2012 at 7:51
  • 1
    $\begingroup$ 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. $\endgroup$
    – S. Carnahan ♦
    Commented Dec 18, 2012 at 16:05

3 Answers 3

Reset to default
7
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ What is [Ko91]? $\endgroup$
    – Alexandre Eremenko
    Commented Dec 17, 2012 at 1:45
  • $\begingroup$ It is the book I cited in my answer. $\endgroup$
    – Andrej Bauer
    Commented Dec 17, 2012 at 4:30
  • $\begingroup$ 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$. $\endgroup$
    – Alexandre Eremenko
    Commented Dec 17, 2012 at 6:33
  • 5
    $\begingroup$ 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. $\endgroup$
    – Robert Israel
    Commented Dec 17, 2012 at 6:55
3
$\begingroup$

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...

Improve this answer
$\endgroup$
2
$\begingroup$

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.

Improve this answer
$\endgroup$
8
  • $\begingroup$ $\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)$?? $\endgroup$
    – Suvrit
    Commented Dec 16, 2012 at 20:21
  • 1
    $\begingroup$ But multiplication of $n$-digit integers is $n^{1+o(1)}$ using Schönhage–Strassen and similar algorithms. $\endgroup$
    – Robert Israel
    Commented Dec 16, 2012 at 20:25
  • $\begingroup$ Ah, I see. Thanks for the clarification Robert. $\endgroup$
    – Suvrit
    Commented Dec 16, 2012 at 20:33
  • $\begingroup$ 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. $\endgroup$
    – François G. Dorais
    Commented Dec 16, 2012 at 20:36
  • $\begingroup$ Andrej, I did NOT ask anything about the exponential function. $\endgroup$
    – Alexandre Eremenko
    Commented Dec 16, 2012 at 21:38

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .