FOM: Complexity Theory

[Joseph Shoenfield]

     I think Fenner's statement that complexity theory is really two
subjects, low-level complexity and structural complexity is an excellent
point.   I think people writing about complexity theory should state which
they are talking about (unless they think their point applies to both).
In the few things I said about complexity theory, I was really talking
about structural complexity.   I have much more interest in structural
complexity, not because I think it is better, but because it is much
nearer to the type of recursion theory in which I have worked.
     In discussing the change-of- name controversy, Fenner discusses 
the possible name-change of the recursion theorem to the fixed point
theorem.   I oppose this for the same reason that I oppose the other
changes: well-established terminolgy should not be changed without
compelling reasons, and the fact that another terminology describes the
situation better is not compelling.   The circumstances under which this
possible name-change arose are briefly described in a footnote to my
article on Kleene's work in the first issue of the ASL Bulletin; I think
anyone who is aware of these circumstances would be embarrassed to support
this particular name-change.