FOM: recursion theory and complexity theory: the sociological aspect
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
> 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.
More information about the FOM