FOM: recursion theory and complexity theory: the sociological aspect

[Stephen Fenner]

On Wed, 9 Sep 1998, Stephen G Simpson wrote:

> 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?
> 

There are some who work in both, but overall, there is a definite
sociological gap.

> 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?
> 

I'd say it is much easier to be a "pure" recursion theorist (with no
interest in complexity, i.e., resource bounds) than it is to be a "pure"
complexity theorist (with no interest in recursion theory).  So many of
the techniques of complexity theory are borrowed from recursion theory,
but I don't know of any techniques developed in complexity that have been
useful in recursion theory.  (cf. John Case's nice examples of
priority arguments in a previous posting, and I know of a few others.)
This may not be surprising considering the
relative ages of both disciplines, but it is even hard for me to imagine a
complexity theoretic idea being applied in pure recursion theory.  It only
stands to reason then that there are so many true-blooded recursion
theorists who have no interest in the other stuff.

But besides the P=NP question, there are some other areas of connection
between the two disciplines, such as inductive inference and other kinds
of machine learning, and a number of researchers have worked on problems
that are interesting whether or no you impose resource bounds, such as
bounded oracle queries, frequency computations, and other things with a
combinatorical flavor.  I'd be interested in hearing other opinions by
people who have worked in both fields.  People like Slaman, Maass, Kummer,
Gasarch, and others too numerous to mention.

Steve F