Why is PARITY ¬in AC0 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 non-theorist.
- PARITY ¬in AC0 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 non-theorists in a course.
- PARITY ¬in AC0 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 AND-OR-NOT circuits for PARITY, and does this result tell them why they cannot? Are there other lower bounds that are corollaries of PARITY ¬in AC0 that give lower bounds on problems people really want to solve? I ask this non-rhetorically.
- 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?).
And of course, for course content, the question is important? compared to what?