FOM: Complexity theory

[Joseph Shoenfield]

     Steve Cook's understanding of complexity theory is infinitely
superior to mine, and I take his posting as a correction of a not too
deeply considered posting of mine.   I think there is a general lesson to
be learned from this posting and much else that has recently appeared in
fom.   The classification of logic into topics and subtopics is not a
search for the truth but an useful aid to logicians.   Comparing the
theorems and techniques of complexity theory with those of recursion
theory can be very helpful in understanding both subjects and in
suggesting directions for future work.   Anyone who thinks he can give a
yes or no answer to the question of whether complexity theory is part of
recursion theory which will be valid for all time is doomed to
disappointment.