FOM: Re: recursion/computability/complexity theory

[Stephen Fenner]

On Wed, 2 Sep 1998, Harvey Friedman wrote:

> Contemporary recursion theory seems to me to be based on rather
> sophisticated and involved elaborations of the priority method to obtain
> structural information about degrees and r.e. sets. What do you view is the
> relevance of this and the techniques involved for questions such as P=NP? I
> am aware that the basic setups in structural complexity have real
> similarity to some of the basic setups in recursion theory, and came after
> them. But, specifically, do you think that someone trying to solve such
> questions as P=NP should be well advised to be steeped in contemporary
> recursion theory?
> 

Specifically for the P=NP and other such basic problems ... no.  At this
point, no one knows what techniques, if any, will solve the P=NP question,
but it's pretty clear that recursion theoretic techniques will not, since
they all relativize (e.g., relativized recursion theorem, etc.).  These
techniques have done a lot to clarify the structure of the polynomial time
(p-time) classes and degrees, however, and they definitely help in
asking the right questions.  For example, a result of Kurtz, Royer, and
me says that all p-time 1-degrees and p-time isomorphism types coincide
iff P=PSPACE.  There are lots of other very interesting results in
complexity that are either direct analogues to statements in recursion
theory or are proved using its techniques (e.g., priority arguments).
They give us a good picture of the world if P != NP, and another good
picture of the world if P == NP.  All this sheds light on the original
question but doesn't solve it.

> Do you perceive a difference in the extent and/or nature of the connections
> the two fields have with other areas of mathematics, science and
> engineering?

Recursion theory is certainly more closely related to fom than complexity.
Besides the P=NP question, much of complexity is motivated by
looking at real-world hardware and software (circuits, binary decision
diagrams, etc.).  There are also some close connections between complexity
and definability with finite models (descriptive complexity).

> > >These algorithms may be showing that one
> >particular degree is higher than another, and both may be noncomputable.
> >I consider *relative* computation to be computation just as much as
> >absolute computation, and so much of recursion theory (at least classical
> >recursion) is still about computation.
> 
> Are you implicitly suggesting another name: relative computability theory?

Hmm ... too many words.  Computation with or without an oracle is still
computation in my mind.  Formally, it has instructions, memory usage,
inputs and outputs.  The 'relative' modifier is only a technical
distinction within the theory.

Actually, I think the best name is "theory of computation," although lots
of CS departments use that for the name of their undergrad theory course
regardless of its content.  I'm only suggesting that given a choice
between 'recursion' and 'computability' to name the theory, the latter
seems more descriptive to me.

Steve

Computer Science Department
University of South Carolina
fenner at cs.sc.edu
http://www.cs.sc.edu/~fenner