[FOM] Complexity of notions/intermediate degrees
Timothy Y. Chow
tchow at alum.mit.edu
Thu Mar 3 13:44:08 EST 2005
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
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.
More information about the FOM