FOM: recursion theory and complexity theory: the sociological aspect

[Stephen G Simpson]

Some people have argued that it's pointless to try to decide whether
complexity theory is part of recursion theory.  I disagree.  For
example, if we are going to discuss a serious question such as

  What are the most important open problems in recursion theory?

then obviously we need to know whether P=NP is in the scope of the
question.  And such questions are recognized as important; Steffen
Lempp et al are busily trying to answer this very question, in
preparation for their upcoming recursion theory meeting.  Other
serious issues such as

  What are the major themes and research programs in recursion theory?

are likewise affected.

However, in deference to the naysayers, let us temporarily stop
examining these serious issues.  Instead, let us examine the
sociological aspect.  Let us discuss questions such as: Do recursion
theorists and complexity theorists work together in mutually
reinforcing harmony?  Or is the actual situation somewhat different?

Bob Soare's 1995 position paper hints at very strong connections
between recursion theory and complexity theory, but in the
sociological aspect this does not appear to be the case.  It seems to
be belied by sociological observations.  I have attended several
recursion theory meetings in recent years, some of them organized by
Bob Soare himself.  I have observed that these meetings included
nothing on complexity theory, not even one talk.  I have the very
strong impression that recursion theorists (Bob Soare's circle) have
absolutely no meaningful interaction with complexity theorists (Steve
Cook's circle).

Is that impression correct?

-- Steve