# 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$.
• At first glance, it doesn't seem likely that the problem is in P. If you are to compute each tower, which is only too likely in a worst-case scenario, you will need at least exponential space. For example, to write $a^b$ you need $b\log(a)$ of space, and $b$ is exponential w.r.t. $\log(b)$, which is the size of $b$. I think that in general you will need something like $\exp(\exp(\cdots\exp(c)\cdots))$ in space, where $c$ is the topmost element of the tower ($a_n$ or $b_m$), so the height of the tower is, I think, $n$. Jan 28, 2012 at 17:46