Intereting Posts

Where in the analytic hierarchy is the theory of true set theory?
What are some interpretations of Von Neumann's quote?
What is the highest power of 2 dividing 100!
Points in general position
Complex Analysis Books
Limit of Multivariate Probability Density Function as one or more or all variables approach positive or negative infinity
Prove by induction. How do I prove $\sum\limits_{i=0}^n2^i=2^{n+1}-1$ with induction?
Riemann integrable function
How to learn from proofs?
Arranging the word 'MISSISSIPPI'
Move the last two digits in front to multiply by $6$
Model of Robinson Arithmetic but not Peano Arithmetic
Repeatedly taking mean values of non-empty subsets of a set: $2,\,3,\,5,\,15,\,875,\,…$
Convergence of a sequence, $a_n=\sum_1^nn/(n^2+k)$
Parallel vector fields imply a flat connection?

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

- How to accurately calculate the error function erf(x) with a computer?
- Any problem computable in $k$ memory slots can be computed with polynomials.
- Algorithm to get the maximum size of n squares that fit into a rectangle with a given width and height
- Calculation of product of all coprimes of number less than itself
- Finding an MST among all spanning trees with maximum of white edges
- Number of integer solutions: $x^2 + y^2 + z^2 = N$

- Efficiently calculating the logarithmic integral with complex argument
- An algorithm for making conditionally convergent series take arbitrary values?
- Increase by one, Shortest path, changes the edges or not?
- nth convolved Fibonacci numbers of order 6 modulo m
- How to Solve this Boolean Equations?
- Algorithmic Analysis Simplified under Big O
- Find the minimum number of links to remove from digraph to make it acyclic
- Recurrence relation using substitution method
- Computational complexity of least square regression operation
- Fermats Little Theorem

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.

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.

My approach is similarly numeric to Leonid’s, but more precise and perhaps easier to analyse. It supports real exponents > 0.

The idea is to represent power towers as a single floating point number with $n$ exponentiations: $(x\mid n) := exp^n(x)$. Normalizing $x\in[0,1)$, this format allows easy comparison between numbers.

What remains is a way to calculate $a^{(x\mid n)}$ for any real, positive $a$. My Python code below is an attempt to do so, while being as numerically stable as possibly, e.g. by using the log-sum trick. My code runs in time proportional to the height of the tower (number of `apow`

calls) and the iterated-log of it’s value (number of recursive calls).

I haven’t been able to find two towers with values close enough to case my method to fail. At least for integer exponents. With fractional exponents it is possible to create very towers too close for my representation to handle. E.g. $$ 2^{2^{2^{2^0}}} \\

< \\

2^{2^{2^{2^{(1/2)^{2^{2^{2^2}}}}}}} $$

I would be interested in suggestions to other types of counter examples, especially integer ones.

It seems to me that for the problem to be in P, we need to non-numerical methods. It doesn’t seem unlikely at all, that certain analytical cases are harder than P.

```
from math import log, exp
def normalize((x,n)):
""" Adjusts n to put x in the range [0,1) """
if x >= 1: return normalize((log(x),n+1))
if x < 0: return normalize((exp(x),n-1))
return (x,n)
normdec = lambda f: lambda *a: normalize(f(*a))
@normdec
def apow(a,(x,n)):
""" Calculates a^(x|n) """
if a == 1: return (1,0)
if a < 1: return (rpow(x,n)*log(a), 1)
if n == 0: return (x*log(a), 1)
if n >= 1:
y, k = cpow(log(log(a)), x, n-1)
return (y, k+2)
@normdec
def cpow(c,x,n):
""" Calculates (x|n) + c """
if c == 0: return (x, n)
if n == 0: return (x + c, 0)
z = rpow(x,n-1)
if z <= log(abs(c)):
return (exp(z)+c, 0)
if c < 0: y, k = cpow(log(1-exp(log(-c)-z)), x, n-1)
if c > 0: y, k = cpow(log(1+exp(log(c)-z)), x, n-1)
return (y, k+1)
def rpow(x,n):
""" Calculates (x|n) as a float
Returs Infinty if the value is out of range"""
try:
for _ in range(n):
x = exp(x)
except OverflowError:
# We get into this case in two situations
# 1) We are calculating log((x|n) + c) and c contributes very little
# 2) We are calculating a^(x|n) for a < 1 and (x|n) is so small it doesn't
# fit into a float
return float('inf')
return x
def powtow(bs):
""" Calculates b[0]**b[1]**b[2]**...**b[m-1] in the (x|n) form.
Equivalent to `foldr apow (1,0) bs'
e.g. apow(b[0], apow(b[1], apow(b[2], (1,0)))) """
if not bs: return (1,0)
return apow(bs[0], powtow(bs[1:]))
if __name__ == "__main__":
print powtow([1,2,3,4,5])
print powtow([2,3,4,5])
print powtow([5,4,3,2])
print powtow([4,4,3,3,3])
print powtow([3,3,3,3,3])
print powtow([4,6,8,8,9])
print powtow([2,2,5,2,7,4,9,3,7,6,9,9,9,9,3,2])
print powtow([3,3,6,3,9,4,2,3,2,2,2,2,2,3,3,3])
print powtow([2,3,2,3,5,8])
print powtow([3,2,2,7,6,7])
print powtow([2,2,2,2,2,2,2,2,2,2,2,2,2,2,4,2,2,2])
print powtow([2,2,2,2,2,2,2,2,2,2,2,2,2,2,4,16])
print powtow([9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9])
print powtow([1.54090919967, 1.46228204461, 1.78555495826, 1.75545819035, 2.21730941808, 1.0797564499, 7.90630125423, 0.881978093585, 1.75085618709, 2.23911325176, 1.39697337886, 1.16053659586, 1.5939192079, 6.11401961748, 0.844860266481, 1.92758094038, 4.64573316954, 0.870819420274, 1.49026447511, 1.77839910981, 1.46208378213, 2.29956158055, 1.00884903003, 1.77521724246, 2])
print powtow([2.32185478602, 1.88198918762, 2.27614315145, 1.77518235487, 1.4841479727, 0.563158971798, 0.732132856919, 0.669957968262, 2.16345101714, 2.23185963501, 0.824885385628, 0.873101580546, 1.45714899023, 2.3973000247, 0.507154709525, 1.94022843601, 1.29982267606, 0.578058713016, 1.58207655843, 1.79417433851, 1.18630377782, 1.37314328673, 0.655551609076, 1.57569812897, 1])
print powtow([2, 2, 2, 1])
print powtow([2, 2, 2, 2, .5, 2, 2, 2, 2])
flip = lambda (a,b): (b,a)
snd = lambda (a,b): b
import itertools
f = lambda xs: [1./x for x in xs]
# Print all power towers of permutations [2..6], sorted
print list(reversed(sorted((flip(powtow(p)),p) for p in itertools.permutations(range(2,7)))))
# Print all power towers of permutations [1/2..1/6] sorted
print list(reversed(sorted((flip(powtow(f(p))),p) for p in itertools.permutations(range(2,7)))))
```

**Examples:**

```
powtow([2,2,2,2,2,2,2,2,2,2,2,2,2,2,4,2,2,2]) = (0.1184590219613409, 18)
powtow([9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9]) = (0.10111176550354063, 18)
powtow([2,2,5,2,7,4,9,3,7,6,9,9,9,9,3,2]) = (0.10111176550354042, 17)
powtow([3,3,6,3,9,4,2,3,2,2,2,2,2,3,3,3]) = (0.19648862015624008, 17)
```

**Counter examples:**

```
powtow([2,2,2,2,2,2,2]) = (0.8639310719129168, 6)
powtow([3,2,2,2,2,2,2]) = (0.8639310719129168, 6)
```

I believe this is going to be much much harder than P, even with suitable bounds on the $a_i$ and $b_i$ introduced. Without them, it is trivially beyond any bounded complexity as one needs to at very least compare $a_1$ and $b_1$.

This is just a really rough idea and might not ultimately work out, but consider representing arbitrary games through power towers, with a certain number of levels representing the game decision tree. So if that tree is just exponential in size for a game, we can fit all move outcomes into a fixed number of levels and can then add several sets of these levels on top to determine alternating moves for both players and have the one result larger than the other if that player has a winning strategy. There are many games that are at very least PSPACE-complete where the site of the decision tree for possible moves is (multi-)exponentially limited, and I believe some are much harder (GO for instance is, with suitable generalisation, EXPTIME-complete, and from intuition, I would expect the decision tree to be exponentially limited with regards to the board size).

A vague answer, I realize, but maybe someone more familiar with complexity theory can say if that thought makes sense.

- Subgroups of $S_4$ isomorphic to $S_3$ and $S_2$?
- Irreducibility in $\mathbb{F_2}$ and field extensions
- factorization of 2 numbers
- If coefficients of the Quadratic Equation are in AP find $\alpha+\beta +\alpha\beta$.
- Show that $f^{(n)}(0)=0$ for $n=0,1,2, \dots$
- Is the sphere with points deleted a topological group?
- Measure theory, measurable function, constant almost everywhere
- Can't understand this pseudo-inverse relation.
- Resource for Vieta root jumping
- Using Nakayama lemma to prove that surjective implies injective.
- row operations, swapping rows
- Mathematical Analysis advice
- Multiple integrals involving product of gamma functions
- Biggest powers NOT containing all digits.
- The square of an integer is congruent to 0 or 1 mod 4