FOM: Complexity Theory

[Stephen Fenner]

On Fri, 4 Sep 1998, Stephen Cook wrote:

> 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.
>

I'll admit the distinction is blurry at times, and the ultimate goals are
certainly the same: separating complexity classes.  I think the
distinction is more a sociopolitical one: I've seen people working in one
of the areas who have little knowledge of the other, and who don't see
much relevance in the other (despite their lack of knowledge).  That's a
shame, because combining the two techniques can (and has) lead to some
spectacular results, of which Razborov and 
Ajtai-Furst-Saxe-Sipser-Yao-Hastad are good examples.

Stephen Fenner                       803-777-2596
Computer Science Department          fenner at cs.sc.edu
University of South Carolina         http://www.cs.sc.edu/~fenner
Columbia, SC  29208  USA