[FOM] Complexity of notions/intermediate degrees

[Timothy Y. Chow]

Some weeks ago Joe Shipman wrote:

>Here's a possibly easier question.  Does there exist a specific natural 
>algorithmic problem whose best known algorithm has an "intermediate" 
>complexity?  By this I mean that the running time f has the property 
>that, for some n>1, the n-fold composition f(f(f(...f(f(x))...) is 
>approximately exponential.

The best known algorithms for factoring m have time complexity that is 
roughly exp((log m)^e (log log m)^(1-e)) for some e strictly between 0 and 
1.  I don't think this quite satisfies your definition of "intermediate" 
(with x = log m) but morally speaking it seems to be intermediate.  But 
algorithms for factoring continue to improve.

>The difficulty of finding such a problem is related to the difficulty of 
>proving a "gap" between P and NP, I think

Why do you think this?  There is no difficulty in proving the time 
hierarchy theorem and hence separating P from EXP, even without any 
natural examples of intermediates.  So it's not clear to me why the 
shortage of natural intermediates between P and NP is related to the 
difficulty of proving P and NP.

Tim