How to test if the power of some algebraic number is the rational combination of two specific algebraic numbers? Suppose we are given three algebraic numbers $\alpha,\beta,\gamma$ by presenting their minimal polynomial (degree less than $m$), the goal is to compute all positive integers $n$ such that $\alpha^n$ lies in the rational combination of $\beta,\gamma$.
Does there exist polynomial time algorithm for this problem?
 A: Here are some thoughts based on exploiting "special structure" (as alluded to in Terry Tao's comments).
Firstly, here is an argument without reference to Skolem-Mahler-Lech for why there
is unlikely to be a polynomial-time algorithm, by considering a very special case:  if $\beta, \gamma \in \mathbf{Q}^{\times}$ then the problem amounts to the 
question of whether $\alpha^n$ is rational for some $n>0$. 
Once we have integrally scaled $\alpha$ to be an algebraic
integer and have factored the constant term of the minimal 
polynomial of $\alpha$ into prime powers up to a sign, which admittedly is not something known in polynomial time, then prime ideal factorization of rational
primes in number fields would take care of this special case.  Do you know a way to handle this special case by good use of algebraic number
theory avoiding non-polynomial time algorithms?
Back to the original problem. 
Assume for specificity that a finite extension $K$ of $\mathbf{Q}$ has been given (say by presenting the minimal polynomial of a primitive element for it), and let $\alpha, \beta, \gamma$ be three given elements of $K$ for which the question is posed. (As noted in my comment above, one cannot pin down the question by merely specifying the minimal polynomials of these three elements over $\mathbf{Q}$.)
We may as well assume $\alpha \ne 0$ and at least one of $\beta$ or $\gamma$ is nonzero.  If $\beta$ and $\gamma$ are $\mathbf{Q}$-linearly dependent then you are just picking a $\mathbf{Q}$-line $L$ in $F$ and asking for which $n > 0$ the power $\alpha^n$ lies in $L$. A necessary and checkable condition is that $L \subset \mathbf{Q}(\alpha)$.  Assume this holds, you're just picking a rational line $L$ in $\mathbf{Q}(\alpha)$ and asking for which $n > 0$ the power $\alpha^n$ lies in $L$.  Likewise, the case when $\beta$ and $\gamma$ are $\mathbf{Q}$-linearly independent amounts to picking a plane $P$ in $F$ and asking which powers $\alpha^n$ with $n > 0$ lie in $P$.  A necessary and checkable condition is that $P \cap \mathbf{Q}(\alpha)$ is nonzero.  Assuming this holds, if that (computable) intersection is a line then it becomes the previous question.  Otherwise the intersection exhausts the plane $P$ and one instead is faced with the analogous question for $\mathbf{Q}$-planes inside $\mathbf{Q}(\alpha)$.
So, finally, $\beta$ and $\gamma$ are sort of red herrings. The problem is really about $\alpha \ne 0$ and its associated finite extension $\mathbf{Q}(\alpha)$:  given a proper $\mathbf{Q}$-linear subspace $V \subset \mathbf{Q}(\alpha)$ of dimension 1 or 2, how do we find those $n > 0$ such that $\alpha^n \in V$?  A cruder question is to determine if there is even one such $n$.  It is easy to figure out if $\alpha$ is a root of unity, and when so then the entire problem is simple, so we assume $\alpha$ is not a root of unity. 
Let's make the following hypothesis (informally stated; experts in algorithms can add precision):
H: There is a "reasonable algorithm" to determine if there is even one such $n$.
If some $\alpha^n$ is rational with $n>0$ (which we can figure out using the "reasonable algorithm" from Hypothesis H for $\mathbf{Q} \subset \mathbf{Q}(\alpha)$) then everything is clear, so we may assume none of these are rational. 
In particular, if $\dim V = 1$ then there is at most one such $n$, and whether
there is one is something we can determine via Hypothesis $H$.  So we now focus on the more interesting case $\dim V = 2$.
The problem of whether there are infinitely many such
$n$ or not, and the determination of all of them in the "infinite" case, can be carried out as follows.
First, run the "reasonable algorithm" from Hypothesis H. If it comes up empty then we're done.  So assume we find such an $n_0>0$, and take it to be minimal. We can replace $V$ with $\alpha^{-n_0}V$, so now $1\in V$.
Run the algorithm from Hypothesis H for this new $V$.  If it comes up empty then we're done (just the initial $n_0$ works).   Suppose it comes up positive, 
so we may find $n_1 > 0$
such that $\alpha^{n_1} \in V$. Together with 1 this must give a 
$\mathbf{Q}$-basis of $V$; take $n_1$ to be minimal. If $\alpha^{n_1}$ is quadratic over $\mathbf{Q}$ (easy to figure out) then the possible $n$'s are 
$n_0 + mn_1$ for $m \ge 0$.
Thus, we now may assume the
$\mathbf{Q}$-degree of $\alpha^{n_1}$ is larger than 2, so $V$ is not a subspace of $\mathbf{Q}(\alpha)$ over any nontrivial extension of $\mathbf{Q}$.
We claim that there are at most finitely many $n>0$ for which $\alpha^n \in V$. This will be proved by contradiction. Suppose that $V$ were to contain $\alpha^n$ for infinitely many $n>0$.  By the non-effective Skolem-Mahler-Lech theorem there would then have to be integers $a > 0$ and $b$ such that 
$\alpha^n \in V$ for $n = am+b$  with all sufficiently large $m$.  But the condition that $\alpha^{am+b} \in V$ for all large $m$ implies that $\alpha^{-b}V$ contains the $\mathbf{Q}$-span of all powers $(\alpha^a)^m$ for sufficiently large $m$, and that span is exactly the field $\mathbf{Q}(\alpha^a) \ne \mathbf{Q}$ (regardless of the lower bound imposed on $m$).  Hence, $V$ would have to contain a line over this subfield $\mathbf{Q}(\alpha^a) \subset \mathbf{Q}(\alpha)$, but $V$ is only 2-dimensional over $\mathbf{Q}$ and we have already arranged that it is not a subspace of $\mathbf{Q}(\alpha)$ over any subfield larger than $\mathbf{Q}$, so we have reached a contradiction. 
So granting Hypothesis H, at least determining whether there are infinitely many such $n$ or not, and the complete determination of all $n$ in the "infinite" case (always exactly an arithmetic progression) can be handled.

But actually for "generic" $\alpha$ only finitely many such $n$ can exist 
for each proper subspace $V$ of $K := \mathbf{Q}(\alpha)$. More specifically, if $|\cdot|_1, \dots,
|\cdot|_{r_1+r_2}$ are the absolute values on $K$ arising from its $r_1+r_2$ embeddings into $\mathbf{C}$ taken up to complex conjugation
then (for fixed but arbitrary $V$) there are only finitely many such $n$ whenever some $|\alpha|_{i_0}$ is strictly larger than $|\alpha|_i$ for all $i \ne i_0$.  
To see this, we may increase $V$ to be a hyperplane, so it is the kernel of a nonzero rational linear form $\ell$ on $K$.  We may write $\ell(x) = {\rm{Tr}}_{K/\mathbf{Q}}(bx)$ for some $b \in K^{\times}$.
Via the $\mathbf{R}$-algebra decomposition $K \otimes_{\mathbf{Q}} \mathbf{R} \simeq \mathbf{R}^{r_1} \times \mathbf{C}^{r_2}$, $\ell_{\mathbf{R}}$ becomes 
$$(x_1,\dots,x_{r_1+r_2}) \mapsto \sum_{i=1}^{r_1} b_i x_i + \sum_{i=r_1+1}^{r_1+r_2} (b_i x_i + \overline{b}_i \overline{x}_i)$$
where $\{b_i\}$ are the nonzero images of $b$ under the $r_1+r_2$ embeddings
(taken up to complex conjugation). 
If $\alpha^n \in V$ with $n > 0$ then
$$0 = \ell(\alpha^n) = \ell_{\mathbf{R}}(\alpha_1^n, \dots, \alpha_{r_1+r_2}^n).$$
If $i_0$ as above corresponds to a real embedding then
$|b|_{i_0} |\alpha|_{i_0}^n \le \sum_{i \ne i_0} 2|b|_j |\alpha|_i^n$,
so $$|b|_{i_0} \le \sum_{i \ne i_0} 2 |b|_j (|\alpha|_i/|\alpha|_{i_0})^n.$$
But $|b|_{i_0} \ne 0$ and $|\alpha|_i/|\alpha|_{i_0} < 1$, so this gives
an upper bound on such $n$'s when $i_0$ is real.
Assume $i_0$ corresponds to a non-real embedding, so instead
$$|b_{i_0} + \overline{b}_{i_0} (\overline{\alpha}_{i_0}/\alpha_{i_0})^n)| \le
\sum_{i \ne i_0} 2|b|_i (|\alpha|_i/|\alpha|_{i_0})^n$$
with $|\alpha|_i/|\alpha|_{i_0} < 1$ for $i \ne i_0$ and $\overline{\alpha}_{i_0}/\alpha_{i_0}$ is a point on the unit circle distinct from 1.  Thus, if arbitrarily large $n$ occur then the right side of this
inequality gets arbitrarily close to 0 and so the points $(\overline{\alpha}_{i_0}/\alpha_{i_0})^n$ on the unit circle for such $n$ become
arbitrarily close to $-b_{i_0}/\overline{b}_{i_0}$.  But Skolem-Mahler-Lech implies that such $n$'s could be taken from all large members of some arithmetic progression, and this would force $\overline{\alpha}_{i_0}/\alpha_{i_0}$ to be a root of unity. Yet if that ratio is indeed a root of unity (something easy to determine algorithmically) then a suitable positive power of $\alpha$ would be real at the $i_0$-embedding, so by replacing $\alpha$ with that power (harmless to do for the purpose of proving the finiteness property) we could also pass to the necessarily proper subfield generated by that power and use degree-induction to conclude.
