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?

wrong, as it makes multiplication by 3 non-computable. $\endgroup$notrational, which (except I confused something) would seem like inevitable to establish any hardness of computation. $\endgroup$12more comments