FOM: Re: recursion/computability/complexity theory

[Harvey Friedman]

Regarding Fenner 5:21PM 9/1/98:

>     There seems to me (and to others) to be a split in complexity
>theory between what I'll call "low level" complexity and "structural"
>complexity.  Low level theory addresses questions about circuits and other
>"hardware-like" things, and depends heavily on combinatorics.  Structural
>complexity deals with more conventional complexity classes (such as P and
>NP) and hierarchies, and borrows a lot of techniques from recursion
>theory.

>     My work is in the latter area, and I find so much of what I do
>recursion-theoretic that the distinction between recursion and complexity
>theory is very blurry for me.

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?

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?

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