FOM: recursion theory and complexity theory: the sociological aspect
Stephen Fenner
fenner at cs.sc.edu
Thu Sep 10 09:19:06 EDT 1998
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
More information about the FOM
mailing list