FOM: Complexity Theory

[Stephen Cook]

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.