As written, the problem requires time $2^{\Omega(m)}$, where $m$ is the length of input (you unfortunately used $n$ for something else). Indeed, if e.g. $\alpha$ is a positive integer (given by its minimal polynomial $x-\alpha$) and $n=0$, the size of the output is exponential in the size of the input. This bound is of course optimal, as there are a number of ways how to compute the result in time $2^{O(m)}$.
Let me try to reformulate the question so that it makes a bit more sense. The main issue is how to choose the representation of the input and output, as well as the notion of approximation, so that exponentiation stands a fighting chance of being computable in polynomial time.
One way was mentioned by Kaveh in the comments: restrict the domain to a fixed finite interval. While this works, it is unnecessarily restrictive; in particular, there is no good way how to transform an algebraic number into one that is bounded so that their exponentials have anything to do with each other.
A more flexible approach is to represent the input as a fixed point number, and the output as a floating point number. To be specific, a fixed point representation is a string
$$\pm a_ra_{r-1}\dots a_0.a_{-1}\dots a_{-s}$$
denoting $\pm\sum_ja_j2^j$, where $a_j\in\{0,1\}$, and a floating point representation is
$$\pm2^e\times a_0.a_{-1}\dots a_{-s}$$
with a similar interpretation, where $e$ is a binary integer, and $a_0=1$. (As an exception, we also allow $0$ to represent itself.) An approximation of a real $x$ to $m$ bits of absolute accuracy is a real $x'$ such that $|x-x'|<2^{-m}$, and an approximation to $m$ bits of relative accuracy is $x'$ such that $|1-x'/x|<2^{-m}$. We will use absolute accuracy for fixed point approximations, and relative accuracy for floating point approximations. It follows that in both cases, we may as well assume $s\le m$ (up to loss of one bit of accuracy).
Fixed point and floating point representations of dyadic Gaussian rationals, and approximations of complex numbers, are defined similarly, using a pair of reals. Everywhere below, $n$ denotes the total size of the input.
Now, let (real or complex) exponentiation be the following problem: the input is a fixed point representation of a number $x$ and a unary natural number $m$, and the output is a floating point approximation of $e^x$ to $m$ bits of relative accuracy. Dually, logarithm takes as input a floating point number $x$ and unary $m$, and the output is a fixed point approximation of $\log x$ (say, the principal branch in the complex case) to $m$ bits of absolute accuracy.
As long as we stick to run-time bounds satisfying some mild regularity conditions, and ignore constant multiplicative factors, we have:
- The complexity of exponentiation, logarithm, or any similar analytic function, is at least the complexity of integer multiplication: e.g., we can read off $a^2$ from $\exp(a2^{-t})=a2^{-t}+a^22^{-2t-1}+O(a^32^{-3t})$ for sufficiently large $t$, linear in the length of $a$.
- Exponentiation and logarithm have the same complexity. The reason is that we can compute the inverse of a nice function by Newton iteration (or more sophisticated methods such as in Brent) using evaluation of the function itself. The iteration typically involse multiplications or divisions, but we can afford these by the previous point.
As for algebraic numbers $\alpha$, they can be represented by their minimal polynomial $f$ (written as a sequence of integer coefficients in binary) together with some means to distinguish between the roots of the same polynomial. A natural way to do that is to require an isolation interval or disk: a pair of fixed point numbers $c,\rho$ such that $|c-\alpha|<\rho$. We need to at least require that $\alpha$ is a unique root of $f$ with this property, but something stronger may be more suitable. More on that later.
Let algebraic number approximation be the following problem: given an algebraic number $\alpha$ in the representation above, and $m$ in unary, compute a (complex) fixed point approximation of $\alpha$ to $m$ bits of absolute accuracy.
$\DeclareMathOperator\re{Re}$The original question asked for $\re e^\alpha$, but let me ignore that for now, and define algebraic number exponentiation as the following problem: given $\alpha$ and $m$ as above, compute a (complex) floating point approximation of $e^\alpha$ to $m$ bits of relative accuracy.
Fact: Up to linear factors, the complexity of algebraic number exponentiation is the same as the complexity of algebraic number approximation plus the complexity of complex exponentiation.
Proof sketch: On the one hand, we can first compute the fixed point approximation of $\alpha$ and then exponentiate it. Note that $m+O(1)$ bits of absolute accuracy for $\alpha$ determine $e^\alpha$ to $m$ bits of relative accuracy, and vice versa.
On the other hand, if we can do algebraic number exponentiation, we can also do plain exponentiation, as we can readily convert a fixed point number (considered exact) to its representation as an algebraic number. By the comments above, this means we can also compute logarithms in the same time bound. Thus, we can approximate an algebraic number by first approximating $e^\alpha$, and then taking a logarithm. QED
This splits the question to two quite unrelated problems. The best known upper bound on exponentiation is
Theorem (Brent): If we can multiply $n$-bit integers in time $M(n)$, we can compute complex exponentiation (and logarithm) in time $O(M(n)\log n)$.
The best known lower bound is the $\Omega(M(n))$ mentioned above. The best known upper bound on $M(n)$ is $n\log n\,2^{O(\log^*n)}$ by Fürer’s algorithm.
Figuring out the state of art for algebraic number approximation (that is, root finding) is rather harder, as it is still an area of active research, and the formulations of bounds in the literature are often not as clear as one would want them. Let $\tilde O(f(n))$ denote $O(f(n)\mathrm{polylog}(f(n)))$.
For real root approximation, Pan and Tsigaridas give:
Theorem: Real algebraic number approximation can be done in time $\tilde O(d^2\tau+dm)$, where $d=\deg(f)$, and $\tau$ is maximum of bit-lengths of the coefficients of $f$.
In the same paper, they mention $\tilde O(d^3+d^2m)$ as the best known bound for complex root approximation. In a slightly more recent paper (http://arxiv.org/abs/1404.4775), they seem to claim the same bounds for the complex case as for the real case, under the assumption that the given isolation disk has isolation ratio (the distance of the disk’s center to the nearest other root of $f$ divided by the radius of the disk) at least $1+1/\log d$ or so, but it’s written in a rather messy way and I may misinterpret it.
Now, the final complication. I defined the problem as approximation of $e^\alpha$, whereas the question asks for $\re e^\alpha$. This actually makes the problem harder: if $\re e^\alpha\ll\operatorname{Im}e^\alpha$, then an approximation $x+iy$ of $e^\alpha$ to $m$ bits of relative accuracy has error $y2^{-m}$, which may well be larger than $x$ itself, and in any case is not guaranteed to be bounded by $x2^{-m}$.
For exponentiation of exact rationals, we can circumvent the problem:
Proposition: Given $\alpha=x+iy$ and unary $m$, where $x,y$ are binary rationals (or exact fixed point numbers), we can compute a floating point approximation of $\re e^\alpha$ to $m$ bits of relative accuracy within the same time bound as complex exponentiation as defined above, up to linear factor. (I.e., $O(M(n)\log n)$ using Brent’s algorithm.)
Proof sketch: We have $\re e^\alpha=e^x\cos y$. We can approximate $e^x$, and floating point numbers are easily multiplied, the problem is to approximate $\cos y$ with relative error $2^{-m}$. We can compute the integer $k$ nearest to $2y/\pi$, whence $\cos y$ is $\pm\cos y'$ or $\pm\sin y'$, where $y'=y-k\frac\pi2$ satisfies $|y'|\le\pi/4$. The issue arises when we need to compute $\sin y'$ and $y'$ is very small, since in order to have $\sin y'$ to $m$ bits of relative accuracy, we need $m+\log|{y'}^{-1}|$ bits of absolute accuracy. Assume that $y=u/v$, where $u,v$ are integers given as input. If $y'$ is small, we have a good rational approximation of $\pi$:
$$\left|\pi-\frac{2u}{kv}\right|\le\frac{2|y'|}k.$$
Now, $\pi$ is known to have a finite irrationality measure $\nu$ (the current bound is $7{.}6063$ by Salikhov). This implies
$$|y'|\ge\frac1{2k^{\nu-1}v^\nu},$$
which gives a linear upper bound on $\log|{y'}^{-1}|$ in terms of the length of the input. We can thus compute $y'$ to the desired accuracy; evaluating $\sin y'$ is then not a problem (if $y'$ is sufficiently small, we can just take $\sin y'\approx y'$). QED
I do not know whether the same holds for algebraic $\alpha$. In the argument above, one can get a bound on $\log|y'|$ from Baker’s theorem, however, none of its versions that I’ve seen is good enough to make the required accuracy linear in the size of the input: in particular, the bounds involve a (rather nasty) polynomial in $\deg(f)$. This makes the resulting algorithm polynomial in the size of the input, but with a ridiculous exponent.
