[FOM] Complexity of notions/intermediate degrees

[Timothy Y. Chow]

On Thu, 3 Mar 2005 JoeShipman at aol.com wrote:
> The reason I think the shortage of natural intermediates is related to 
> the difficulty of separating P from NP is that we don't have a 
> computational operator of intermediate power (to separate P from EXP the 
> strong operator of exponentiation was good enough).  If there were a 
> natural intermediate function, one could construct a natural operator of 
> intermediate power by using it to bound a search, which could lead to a 
> whole in-between-realm of natural functions which are not in P and not 
> NP-complete.  (If the true complexity of SAT is exponential, then 
> factoring could be NP-complete but no function of "intermediate" 
> complexity as I define it could be [at least for many-one reducibility, 
> will need to think about the case of Turing reducibility]).

I think I follow what you say here, except that I still don't see what 
naturalness has to do with anything.  We can, after all, construct plenty 
of unnatural candidates for things intermediate between P and NP-complete. 
Having natural examples would be pleasant, but why would that make proving 
that they're computationally inequivalent any easier?  There is no 
shortage of natural examples of NP-complete problems, but they haven't 
been of much use in proving separation theorems.

Also, using the analogy with recursion theory, the absence of natural 
intermediate degrees hasn't stopped us from proving that there really are 
distinct degrees.

Tim