Complexity class of comparison of power towers Consider the following decision problem: given two lists of positive integers $a_1, a_2, \dots, a_n$ and $b_1, b_2, \dots, b_m$ the task is to decide if $a_1^{a_2^{\cdot^{\cdot^{\cdot^{a_n}}}}} < b_1^{b_2^{\cdot^{\cdot^{\cdot^{b_m}}}}}$.


*

*Is this problem in the class $P$?

*If yes, then what is the algorithm solving it in polynomial time?

*Otherwise, what is the fastest algorithm that can solve it?


Update: 


*

*I mean polynomial type with respect to the size of the input, i.e. total number of digits in all $a_i, b_i$.

*$p^{q^{r^s}}=p^{(q^{(r^s)})}$, not $((p^q)^r)^s$.

 A: Recently I asked a very similar question at Mathematica.SE.
I assume you know it, because you participated in the discussion.
Leonid Shifrin suggested an algorithm that solves this problem for the majority of cases, although there were cases when it gave an incorrect answer. But his approach seems correct and it looks like it is possible to fix those defects. Although it was not rigorously proved, his algorithm seems to work in polynomial time. It looks like it would be fair if he got the bounty for this question, but for some reason he didn't want to.
So, this question is not yet settled completely and I am going to look for the complete and correct solution, and will start a new bounty for this question once the current one expires. I do not expect to get a bounty for this answer, but should you choose to award it, I will add it up to the amount of the new bounty so that it passes to whomever eventually solves this question.
A: For readability I'll write $[a_1,a_2,\ldots,a_n]$ for the tower $a_1^{a_2^{a_3^\cdots}}$.
Let all of the $a_i,b_i$ be in the interval $[2,N]$ where $N=2^K$ (if any $a_i$ or $b_i$ is 1 we can truncate the tower at the previous level, and the inputs must be bounded to talk about complexity).
Then consider two towers of the same height
$$
T=[N,N,\ldots,N,x] \quad \mathrm{and} \quad S=[2,2,\dots,2,y]
$$
i.e. T is the largest tower in our input range with $x$ at the top, and S is the smallest with $y$ at the top.
With $N, x\ge 2$ and $y>2Kx$ then
$$
\begin{aligned}
2^y & > 2^{2Kx} \\
    & = N^{2x} \\
    & > 2log(N)N^x &\text{ as $x \gt 1 \ge \frac{1+log(log(N))}{log(N)}$} \\
    & = 2KN^x
\end{aligned}
$$
Now write $x'=N^x$ and $y'=2^y>2Kx'$ then
$$
[N,N,x]=[N,x']<[2,y']=[2,2,y]
$$
Hence by induction $T<S$ when $y>2Kx$.
So we only need to calculate the exponents down from the top until one exceeds the other by a factor of $2K$, then that tower is greater no matter what values fill in the lower ranks.
If the towers have different heights, wlog assume $n>m$, then first we reduce
$$
[a_1,a_2,\ldots,a_n] = [a_1,a_2,\ldots,a_{m-1},A]
$$
where $A=[a_m,a_{m+1},\ldots,a_n]$. If we can determine that $A>2Kb_m$ then the $a$ tower is larger.
If the towers match on several of the highest exponents, then we can reduce the need for large computations with a shortcut. Assume $n=m$, that $a_j> b_j$ for some $j<m$ and $a_i=b_i$ for $j<i\le m$.
Then
$$
[a_1,a_2,\ldots,a_m] = [a_1,a_2,\ldots,a_j,X] \\
[b_1,b_2,\ldots,b_m] = [b_1,b_2,\ldots,b_j,X]
$$
and the $a$ tower is larger if $(a_j/b_j)^X>2K$. So we don't need to compute $X$ fully if we can determine that it exceeds $\log(2K)/\log(a_j/b_j)$.
These checks need to be combined with a numeric method like the one @ThomasAhle gave. They can solve the problem that method has with deep trees that match at the top, but can't handle $[4,35,15],[20,57,13]$ which are too big to compute but don't allow for one of these shortcuts.  
