## [Computational Complexity] Why is PARITY not in AC_0 important?

Expand Messages
• When discussing what should we teach in a basic complexity course (taken mostly by non-theorists) we often say results such-and-such is important. The question
Message 1 of 1 , Mar 11, 2008
• 0 Attachment
When discussing what should we teach in a basic complexity course (taken mostly by non-theorists) we often say results such-and-such is important. The question then arises- why is it important? Can the reasons be conveyed to a non-theory audience? Lets look at PARITY CANNOT BE COMPUTED BY POLYTIME, AND-OR-NOT, UNBOUNDED FANIN, CONSTANT DEPTH CIRCUITS (henceforth PARITY ¬in AC0).

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.
1. 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.
2. 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.
3. 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.
4. 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
Your message has been successfully submitted and would be delivered to recipients shortly.