FOM: Complexity Theory
jrs at math.duke.edu
Fri Sep 4 11:20:36 EDT 1998
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.
More information about the FOM