FOM: Complexity Theory
Stephen Cook
sacook at cs.toronto.edu
Fri Sep 4 13:44:32 EDT 1998
I don't think that the distinction between low-level and structural complexity
is as clear as Fenner and Shoenfield suggest. The basic goal of both areas
is the same: Separating the fundamental complexity classes, such as NC1, LOGSPACE,
PTIME, NP, PSPACE, etc. I think that Razborov's result giving a superpolynomial
lower bound on the monotone circuit complexity of an NP problem (the clique
function) is an example that blurs the distinction.
An even better example is the superpolynomial lower bounds by Ajtai
and Furst/Saxe/Sipser on the size of bounded depth circuits for computing
the parity of of n input bits. This seems like a low-level result, but FSS
pointed out that if the lower bound could be strengthened, it would lead
to an oracle separtaing the levels of the relativized polynomial hierarchy,
which is surely a structural result. Indeed Yao and Hastad later achieved
the required strengthening.
Steve Cook
----------------
I think Fenner's statement that complexity theory is really two
subjects, low-level complexity and structural complexity is an excelle
nt
point. I think people writing about complexity theory should state w
hich
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 th
e
situation better is not compelling. The circumstances under which th
is
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 thi
nk
anyone who is aware of these circumstances would be embarrassed to sup
port
this particular name-change.
More information about the FOM
mailing list