tag:blogger.com,1999:blog-3722233.post4957718345494186843..comments2020-01-22T05:36:51.857-05:00Comments on Computational Complexity: Why is PARITY not in AC_0 important?Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger8125tag:blogger.com,1999:blog-3722233.post-45611438857339137782008-04-16T15:19:00.000-04:002008-04-16T15:19:00.000-04:00For me this result is important simply because the...For me this result is important simply because there aren't that many unconditional separation/lower bound results in complexity, and it's reassuring to visit at least one proof of impossibility about a natural problem. There are some classical trivial results like the time and space hierarchy theorems, but it's not really very surprising that EXPTIME-complete problems can't be solved in polynomial time. On the other hand, when you pose the problem to someone to attempt to construct polynomial-size constant-depth circuits for parity, you can imagine them struggling for a while with various possible solutions. It has for me the same flavor as pumping theorem results that specific languages are nonregular.Derrick Coetzeehttps://www.blogger.com/profile/05407492273389264037noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-28056657971473352162008-03-11T22:47:00.000-04:002008-03-11T22:47:00.000-04:00On first reading (and first commenting) I missed t...On first reading (and first commenting) I missed the part where Bill says the course is "taken mostly by non-theorists," which makes my previous comment off-topic.<BR/><BR/>I have never designed a complexity course for non-theorists, but one way to go about it would be to have a section on foundations of cryptography, which would be by far the most appealing part of complexity theory for non-complexity-theorists. If one works up to the definition of pseudorandom functions, then it's a small step to do Razborov-Rudich, and at that point proving that parity is not in AC0 would be a good illustration of what kind of lower bounds we know how to prove, and why they end up being "natural." <BR/><BR/>Plus one immediately can see that the lower bound proof is an attack that breaks all block cyphers implementable as bounded-depth circuits, which gives both the Razborov-Rudich argument and the lower bound proof a very concrete flavor.Lucahttps://www.blogger.com/profile/17835412240486594185noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-41094034148428500662008-03-11T21:47:00.000-04:002008-03-11T21:47:00.000-04:00do some people in the real real world really want ...<I>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?</I><BR/><BR/>At the time of FSS there was a general question of whether one could do the same kinds of tricks to get extremely fast multiplier circuits to match fast adders. Parity notin AC^0 showed that this was not possible. <BR/><BR/>There is a weaker version of justification 3: Parity notin AC^0 is a stepping stone to understanding fast parallel computation. I never really bought the "stepping stone to P vs NP" but this seemed a reasonable goal. <BR/><BR/>Why teach it? Because it is important to understand combinatorial/nonuniform models of computation and this is one of the nicest results in dealing with such models. (I guess this is a variant of Bill's reason 2. BTW: Small space TMs - to which AC^0 is compared by Anonymous #1 - are much less natural than clean combinatorial models of computation like circuits. ) The oracle consequence is completely beside the point. For a wider audience, I think it is good to get the understanding the complexity isn't just about TMs. (Though in our quarter-long complexity course we do other things.)Paul Beamenoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-75897202952502319972008-03-11T16:51:00.000-04:002008-03-11T16:51:00.000-04:00I think that the result is a wonderful illustratio...I think that the result is a wonderful illustration of why Complexity is both fascinating and difficult.<BR/><BR/>I would cover the result in the following context: depth 2 AC_0,<BR/>a.k.a. CNF and DNF is clearly interesting and useful (e.g. easy clear proofs that they are universal, used in textbooks, even by engineers as PLAs).<BR/><BR/>PARITY clearly needs exponential size depth 2 circuits (again, intuitive and clear proof for OR of ANDs: each AND must be of maximal length, and all are disjoint). All this formalism collapses for depth 3 or more. Yet the intuition that you cannot compute PARITY remains. The intuition could be based on two "feelings"<BR/><BR/>a. You need to take into account each input--if indegree was 2, we'd need depth log. Unbounded fanin cannot really help that much because you "mix up" many inputs, and for PARITY you can't really do such mixing.<BR/><BR/>b. PARITY wiggles a lot: an AND is like a polynomial, which cannot wiggle exponentially much.<BR/><BR/>Of course neither a. nor b. makes mathematical sense. Yet you can make nontrivial proofs out of them:<BR/><BR/>a. can be formalized as the Sipser-Hastad proof (which is elemenatry, and can be given in a single lecture).<BR/><BR/>For b., as Luca points out, for more sophisticated students, you can give the Fourier proof, that brings in notions of learning, correlation, and pseudo-randomness, all with relatively easy proofs.<BR/><BR/>One can then point out that deep down, a. and b. are the same intuition, expressed in different language.<BR/><BR/>Finally, (for mature audiences only) one can explain natural proofs, and show that the beautiful AC_0 noncontainment proofs have limitations, and going further seems quite difficult.<BR/><BR/>Not bad for a toy complexity class.<BR/><BR/>For non-theorists, selected portions of the above (even just the Sipser-Hastad proof) would give an idea of why questions like P vs NP are difficultJanoshttps://www.blogger.com/profile/07212822875614144307noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-16326506522013550482008-03-11T16:04:00.000-04:002008-03-11T16:04:00.000-04:00The 3rd and 4th reasons are convincing to me, and ...The 3rd and 4th reasons are convincing to me, and I think the 3rd could be convincing to a non-theorist. (Bounding the power of weaker models of computation is certainly a natural approach to try.)<BR/><BR/>Note also that there are lots of things people learn <EM>just because they are interesting</EM>, and not because they have any intrinsic "importance". Sticking to CS courses by way of example, students learn about operating systems and compilers even though very few people are ever going to build one themselves. We teach programming language principles even though most students' jobs are going to have them program in Java or Ruby on Rails. Etc., etc.Jonathan Katzhttps://www.blogger.com/profile/07362776979218585818noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-59699847238366111072008-03-11T15:24:00.000-04:002008-03-11T15:24:00.000-04:00Even real world people (hardware engineers?) or no...Even real world people (hardware engineers?) or non-theorists need some natural metric to compare circuits, and depth is second only to size in this regard. Couple with this the fact that AC_0 has depth constant (and not log^i(n), which sounds fantastic to the real world) - and AC_0 is indeed an important class to lower bound.<BR/><BR/>I do however agree with Bill that an audience (theory or otherwise!) must be told briefly why the result is important, if at all. <BR/><BR/>If a result is not important, but merely interesting, it might be a good idea to mention this explicitly.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-19149480071578890742008-03-11T14:17:00.000-04:002008-03-11T14:17:00.000-04:00None of those reasons are compelling, but I see th...None of those reasons are compelling, but I see the AC0 lower bound as a very good illustration of the natural proof limitations. All AC0 lower bound proofs are "natural," and the one via the switching lemma allows to learn AC0 circuits with queries, so if one has talked about Goldreich-Levin when talking about pseudorandomness (which is a premise for natural proofs) and about Fourier analysis when talking about PCP, everything comes together very beautifully.<BR/><BR/>There is also a meta-point, that complexity theory is still very weak in unconditional results, but very strong in the unexpected connections it has unearthed, but within complexity theoretic questions, and between complexity theory and other fields. So a complexity theory course should too have an emphasis on unexpected connections.Lucahttps://www.blogger.com/profile/17835412240486594185noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-72799278603293530802008-03-11T12:16:00.000-04:002008-03-11T12:16:00.000-04:00Sorry, but you failed to convince me.First of all,...Sorry, but you failed to convince me.<BR/><BR/>First of all, I don't think you really need in a complexity course to give an oracle that separates PH and PSPACE. (I think that separating P, NP, PH is enough for a course for non-theorists. It is easy for them to admit that most of the classes we speak about can be separated after seeing two or three separations)<BR/><BR/>And it's hard to convince a non-theorist that very small classes are interesting.<BR/>I know that my students have difficulty with LOGSPACE, so they will have the same problem with AC0.<BR/><BR/>And I think the real question you have to ask is not "is PARITY notin AC0" important, but rather "is AC0 important" ?<BR/><BR/>Of course, if you speak in your course of AC0, proving that a natural problem is not in AC0 is interesting.Anonymousnoreply@blogger.com