FOM: asymptotic complexity; the sociology of "computability theory"

[Stephen G Simpson]

Joseph Shoenfield writes:
 > The result which pleased me most was a theorem of Mahaffey, which says
 > that if P=NP is false, no sparse set is NP-complete.   A sparse set is a

Do you mean Steve Mahaney?  Yes, it is a very nice result.  And
asymptotic complexity is still a wonderful subject, with a lot of
exciting ideas and techniques being introduced all the time.  (I
recently served on a PhD thesis committee in this area.)  

In my opinion, asymptotic complexity still represents a golden
opportunity for people with a flair for computational theory.  And I
don't think it's an exaggeration to say that it dwarfs degrees of
unsolvability and r.e. sets, according to some very significant
measures.  For one thing, it has a lot of practical significance.  It
is certainly taught to a lot more students, because it is nowadays
considered essential background for analysis of algorithms.  (For
example, I sometimes teach graph theory, and NP-completeness is in the
part of the textbook dealing with graph algorithms.)  It's probably
also a lot bigger with respect to another measure, number of papers
published per year.  (Is there an easy way to demonstrate this?)

The sociology of "computability theory" is interesting to me.  We
could discuss this in terms of leadership struggles, power bases, etc.
I'd like to hear a candid discussion of this.

Let me start off with a conjecture.  I conjecture that Soare and his
group (degrees of unsolvability and r.e. sets) are in something of a
bind with respect to asymptotic complexity and similar computer
science topics.  On the one hand, they want to hint at connections to
computer science, because of the funding issue.  On the other hand,
they are afraid to explicitly embrace subjects like asymptotic
complexity, because they don't want to be the tail wagging the dog.
Does this conjecture sound right?

-- Steve