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$.