When discussing
what should we teach in a basic complexity course
(taken mostly by nontheorists) we often say
results suchandsuch is important.
The question then arises why is it important? Can the reasons
be conveyed to a nontheory audience?
Lets look at
PARITY CANNOT BE COMPUTED BY POLYTIME, ANDORNOT, UNBOUNDED FANIN, CONSTANT DEPTH CIRCUITS
(henceforth
PARITY ¬in AC_{0}).
Why is
PARITY ¬in AC_{0} interesting? important?
(For a good source on this result and other lower bounds on simple
models see
boppana_sipser.pdf
boppana_sipser.ps,
a survey from 1989 which is, sadly, not that dated.)
I
do find the result interesting, but none of the reasons
below seem that satisfying to a nontheorist.

PARITY ¬in AC_{0}
is the way to obtain an oracle that separates PSPACE from PH.
(An oracle to make them collapse is easy.)
Hence no proof that relativizes can be used to seperate
PSPACE from PH (this is not a rigorous concept, but people in
the area have a sense of what it means).
To motivate this you need to do some proofs that
relativize. How many? Perhaps I am biased here I had a course in
computability theory covering 2/3's of Soare's book
(I understood 1/2 of it at the time) before studying complexity
theory, so I really knew what
relativizing technique meant when I looked at oracles.
That level of understanding is not needed, but some is.
Even so, seems hard to get across to nontheorists in a course.

PARITY ¬in AC_{0}
is a natural problem on a natural model
with a
natural proof,
and hence is interesting.
This raises the question: do some people in the real real world really want to construct
polysize constant depth unbounded fanin ANDORNOT circuits for PARITY,
and does this result tell them why they cannot?
Are there other lower bounds that are corollaries of
PARITY ¬in AC_{0} that give lower bounds on problems people really want
to solve?
I ask this nonrhetorically.

One approach to P vs NP is to start with simple
models of computation that one can prove lower bounds in,
and then scale up.
There was more optimism for this approach back in 1989
then there is now.

The techniques used to prove the result are
interesting (YES there are several proofs,
all interesting) and useful for
other theorems of interest (circular reasoning?).
A more general issue: when are results interesting in
their own right, and when are they meant to be
part of a larger research program?
We may not know until many years later.
And of course, for course content, the question is
important? compared to what?

Posted By GASARCH to
Computational Complexity at 3/11/2008 10:54:00 AM