FOM: recursion theory vs. asymptotic complexity theory

[Stephen G Simpson]

Martin Davis writes:

 > Harvey has suggested that recursion theorists would have been well
 > advised to make the switch to asymptotic complexity theory.

I don't think Harvey suggested that the recursion theorists should
have "switched" to asymptotic complexity theory.  Rather, he pointed
out that the recursion theorists overlooked or rejected an excellent
opportunity to *broaden* recursion theory, to include exciting
computational issues which have very substantial points of contact
with computer science, engineering, graph theory, etc.  Instead of
jumping at this opportunity, the recursion theorists remained focussed
almost exclusively on structural questions involving Turing degrees
and r.e. sets.  This narrow niche is interesting, but the law of
diminishing returns may be at work here.

 > If it turns out that P=NP (and who can be sure that it won't), much
 > of the subject will collapse.

This is a good point, but I think it somewhat understates the interest
of the positive results in this field, concerning logspace etc.

-- Steve