Recall that exponent towers are evaluated from the top down, thus

g(n) = n^(lg n) = 2^(lg n)^2,

g(g(n)) = 2^(lg n)^2^2,

and in general an m-times iterated g(n) is given by

g(g(g( ….g(n)…) = 2^(lg n)^2^m = n^(lg n)^(2^m -1).

It is pretty surprising to find a simple expression for an iterated function!

However,

2^(lg n)^p and n^(lg n)^p

are subexponential for any power p, as can be seen by dividing by 2^dn for any positive d, so this family of functions is too small to contain h(n).

If h(n) is written as h(n) = n^k(n), the above results show that

(lg n)^p for any p is a lower bound and n^a is an upper bound for any positive a, giving hope of finding a k(n) that somehow interpolates between (lg n)^p and n^a. Means and geometric means do not work in the n go to infinity limit.

If I get some time and a pot of ultra strength coffee this weekend, I am going to try the family

k(n,b,c) = n^(b/n^c) for positive b and c.

The idea is to be less than n^a in the limit. If there are values of b and c such that h(n,b,c)= n^k(n,b,c) is subexponential, but h(h(n,b,c),b,c) is exponential, we would be pretty close to pinning down h(n).

First I need to work out the algebra of exponent towers.

]]>The simplest one I could come up with is

f(x,a) = x^(x^a) for any a in (0,1).

g(x) = x^(lg x) does not work, because g(g(x)) is still subexponential, in fact x^(lg x)^3.

]]>(not taking anything away from Ryan, but rather to give to a different problem)

]]>Functions are generally classified as:

1. Elementary: What you wind up with if you start with polynomials, exponentials, and logs, and apply +, -, *, /, and root finitely many times. These are in a standard calculus book.

2. Algebraic: Satisfies a polynomial equation, whose coefficients are polynomials in x (the independent variable).

3. Transcendental: Not algebraic. Note that some elementary functions are Algebraic (polynomials, rationals, fractional powers), and some Transcendental (trig, logs, irrational powers).

4. Higher Transcendental: Many references (29 hits on Amazon) have this title. Usually the gamma function is regarded as the “lowest of the higher transcendental” functions, and is Chapter 1.

5. Functions of Mathematical Physics and/or Special functions (441 hits on Amazon): A subset of the Higher Transcendentals that turn up a lot in physics, usually as a result of using separation of variables on the wave, potential, and heat equation in two or three dimensions.

6. Hypergeometric (possibly generalized and/or confluent). An astounding fraction of important functions fit into a simple framework created by Gauss. If you work with them, everything falls into place, and you realize what a sharp guy Gauss was.

Over 100 years ago it was realized that most solutions to ordinary differential equations do not fall into any category of of known functions. All you can do is name the solution, and set to work figuring out some properties and working out suitable approximations. You can do a good job at this; last week a space probe zipped past and photographed a comet that looks like a bowling pin. It was not an accident that it was near by, it was engineers approximating differential equations.

The only thing you know about the half exponential function is that f(f(x)) = 2^x. This probably does not define it uniquely. A pure math question is how smooth a solution there is. At any rate, this is a hard equation to learn much from, and it is a good bet that the solution will be “more transcendental” that the solutions you get from simple differential equations.

So, the likelihood that there is an “elementary solution” is pretty close to 0.0. That just means it is time to figure out some properties. A few power series coefficients at x=0 would be interesting. For TCS purposes, an decent approximation for large x would be almost as good as an explicit formula. For example, a reasonably simple pair of functions g and h such that for large x:

x WLT g(x) LT f(x) LT h(x) WLT 2^x,

(WLT = Way Less Than, LT = Less Than)

would be useful.

]]>I think that one critical point in Ryan’s beautiful work is not emphasized enough: In order to apply Ryan’s technique, you don’t need a (weak) algorithm for deciding circuit satisfiability, but rather a (weak) algorithm for distinguishing an unsatisfiable circuit from a circuit that is satisfied by at least half of its assignments.

Note that the latter distinguishing problem is easily solvable within RP, and the point is that Ryan’s technique requires a weak *deterministic* algorithm.

This fact is important for two reasons:

1. It makes Ryan’s technique much stronger and more applicable, since it is much more plausible to find weak deterministic algorithms for an RP problem than to an NP-complete one (i.e. Circuit-Sat).

2. More conceptually, I believe that Ryan’s technique should be viewed as a very powerful instance of the family of “derandomization implies circuit lower bounds” results. Perhaps other techniques from this family can be combined with Ryan’s work to obtain even stronger results.

]]>No. Only shadows of shadows.

]]>