FOM: Complexity Theory

Stephen Cook sacook at
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
	 point.   I think people writing about complexity theory should state w
	 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
	 situation better is not compelling.   The circumstances under which th
	 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
	 anyone who is aware of these circumstances would be embarrassed to sup
	 this particular name-change. 

More information about the FOM mailing list