FOM: recursion theory vs. asymptotic complexity theory

Martin Davis martind at
Wed Aug 12 14:01:50 EDT 1998

Harvey has suggested that recursion theorists would have been well advised
to make the switch to asymptotic complexity theory. In general, I don't take
kindly to suggestions that scholars would be better advised to work on
something other than what interests them. In this particular case, I can't
help noting that whereas recursion/computability theory BEGAN with a
compelling proof of a separation principle (r.e. vs computable), asympotic
complexity theory has mainly succeeded in posing (admittedly interesting and
important) problems. If it turns out that P=NP (and who can be sure that it
won't), much of the subject will collapse.


More information about the FOM mailing list