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