[FOM] Complexity of notions/intermediate degrees

[JoeShipman@aol.com]

One of Harvey's points here is that sets of integers with intermediate r.e. degrees are TWO levels of complexity away from being nice -- not only are there no natural sets of intermediate degree (while there are specific sets of degree 0' which are pretty simple to define), there are no natural intermediate degrees!  (There are natural sets of intermediate degrees, such as the "low degrees" which are nonrecursive with jump = 0', but that's 2 levels up from sets of integers.)

(Interesting linguistic point:  In the previous paragraph, I used 2 similar phrases "sets of intermediate degree" and "sets of intermediate degrees" which have very different meanings -- the first "of" means "belonging to an" and the second "of" means "whose members are", so the conjunction connects things in opposite directions.)

I conjecture that there DO exist natural intermediate degrees, but that it will require a big breakthrough to find one (ZF might not be enough).

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 difficulty of finding such a problem is related to the difficulty of proving a "gap" between P and NP, I think; and is related at a higher level to the difficulty of finding a natural intermediate degree (and, I informally conjecture, is related at a yet more abstract level to the difficulty of settling the continuum hypothesis).

-- JS