Parity and circuit complexity

Question

attempt to restate question

From the feedback, it is obvious that I have not clearly articulated my point. Also, it is not my intent to be condescending. I very clearly have a notion / idea / question that is contrary to the doctrine subscribed to by the readers of this question. I am genuinely trying to reconcile something that is so incongruent to me that it is difficult to even put in to words. I literally do no know how to express it in a succinct simple paragraph.

This may not help, but let me try an analogy. Let's say that hypothetically there are two different groups, the first one is called 'EE' and the second is called 'CS'. Both groups consider themselves to be authoritative experts in Boolean circuits. As unlikely as it may seem, for some reason the two groups do not speak to each other or read the others results, despite their common interest. There are some differences:

The "EE" group builds boolean circuits. They literally turn theoretical ideas into to something physical. Physical goods mean there are very tangible, objectively unambiguous costs involved.

The "CS" group does not (usually) build circuits. Because nothing is physically produced, the physical resource costs tend to be dramatically lower for the "CS" group, almost to the point where it is "effectively zero."

Although both groups consider themselves boolean circuit experts, there is a curious discrepancy in the choice for their respective "boolean basis." As long as the boolean basis is "complete", that basis can be provably shown to be able to serve as the building block for every possible n-arity boolean function. What is important is that there are a couple of "natural" boolean basis choices, but as long as the boolean basis choice is "complete", the different "natural" choices can all implement all n-arity boolean functions- that is to say, one choice is not "more powerful" or "more expressive" than the other. The "complete" property means that they are "logically identical", despite the seemingly paradoxical fact that they are composed of distinctly different primitives.

Almost since the dawn of building boolean circuits, the "EE" group has consistently and invariably chosen "NAND" (which, to an EE person, there is no need to state the obvious "and NOR" qualification). For the EE group, the reason for this choice is so obvious to them it literally does not occur to them that anyone would make a different choice.

The "CS" group, on the other hand, has chosen "AND, OR, NOT". This choice can express exactly the same n-arity circuits as "NAND", and vice versa, due to the fact that both are a "complete" boolean basis.

The fact that the "EE" group has very real physical costs, which tends to translate directly in to money, means that even though there is no logical difference between a boolean basis choice, if one of the many available choices in any way what-so-ever has a monetary advantage, that's the one that is picked.

Money has a tendency to place a simply enormous pressure to ensure that whatever "choice" is made is the optimal one. It is not hyperbole to say that billions of dollars riding on the decision. It is difficult to put in to words how much pressure and effort goes in to this. There is simply no detail, and the pedantic consequences of every possible permutation of those details, behind choosing "NAND" that is not completely understood and justified.

In my original question, I point out two examples of this: The Apollo Guidance Computer, which made landing on the moon possible, and the Cray-1, the legendary computer by Seymour Cray.

If you are unaware of the details, it is difficult to express what it means to "Space Certify" a design. I think it's safe to say that Seymour Cray is widely recognized to be genuinely gifted at "building circuits". Although it may seem "insignificant", the decision to use 4 / 5 input NAND gates exclusively in the design of the Cray 1 was one of the contributing factors behind its legendary performance.

Again, I sincerely apologize for the lengthy exposition, but based on the responses I can't help but feel that at least some of you do not fully appreciate the significance of the fact that

• There is another group of people who consider themselves "boolean circuit experts".
• This other group of "boolean circuit experts" has consistently, universally, and invariably chosen "NAND" as their boolean basis, despite the fact that there are multiple, equivalent options.
• As near as I can tell, the "CS" group began developing their boolean circuit models (i.e., $AC^0$, $NC$, etc) right around the time the first P vs. NP descriptions and theories began to take form in the 1970's.
• This means that the "EE" boolean circuit theories predate the "CS" boolean circuit theories by decades.
• Yet, despite a rich, mature, and well understood body of work that was available, the "CS" group made the curious decision to go with "AND, OR, NOT".
• At some point, someone in the "CS" group "discovered" that PARITY was not in $AC^0$, and published a peer reviewed paper.

I fully appreciate that all of this sounds completely condescending. This is genuinely not my intent. It's difficult for me to gauge this audience to determine at what point providing the justification for my point turns in to sounding like a condescending ass.

It is fairly obvious that I felt a need to justify my simple question:

The well known result regarding parity and $AC^0$, also taken from from Wikipedia:

The Boolean function PARITY, which is 1 if and only if the sum of its input bits is odd, does not lie in $AC^0$.

My question is: "Why is this considered to be a fundamentally important result?"

Now, I admit, this is an extremely odd question. The reason why I asked it is because, at least for me, I find this detail extremely interesting:

• The people who actually build circuits use NAND as their boolean basis.
• The "CS" theory people choose "AND, OR, NOT".

For me, this stands out like a neon red light. Even if you think I'm completely wrong, I at least hope that you recognize "I wasn't aware of any of this, but now that you mention, it does seem a little bit weird." Experience tells me this usually goes one of two ways:

1. You completely and thoroughly understand the consequences of breaking with the established tradition.
2. You're ignorant of the nuances.

People in the first category are easy to spot. For me, it is simply inconceivable that anyone who truly understood the ramifications of deciding to go with "AND, OR, NOT" instead of "NAND" did not spend 5 minutes doodling out the maximal worst case for 3, 4, etc bits. At which point, you sort of chuckle and say "Man, this is going to totally suck in the XOR corner case."

People in the second category are harder to predict. In the worst case, they spend no effort researching the issue. This is unfortunate because they tend to end up "rediscovering" things that have been known for over 100 years.

This is why I am asking the seemingly "obvious" question. I find it almost impossible to believe that someone in group 1, who truly understood the issues involved, would deliberately and knowingly break with the fully vetted NAND boolean basis without understanding all of the consequences of doing so. It literally takes just a few minutes to work through some corner cases. I simply can not understand how someone who studied the issue would not know that:

• The XOR / PARITY corner case is going to be comically bad.
• Your practical experience tells you that this "effect" does not accurately reflect how XOR / PARITY circuits are built anyways, so it is completely benign and safe to ignore.

On the other hand, there is a peer reviewed, published paper that says "The PARITY / XOR corner case sucks when using 'AND, OR, NOT'." This is a contradiction. How do you completely understand the consequences of breaking with the established norm, and then be "surprised" by something that was hopefully blatantly obvious the moment it was decided to go with "AND, OR, NOT"?

I can't help be get the feeling that this whole "2 input NAND" thing is genuinely novel to you. You do understand what it means, right? The 2 input NAND gate is functionally complete for the entire boolean domain. If you can prove that this simple, 2 input NAND gate has some property, you can prove it for the entire boolean domain. Hypothetically you could do something like this:

• $\{AC^0\} ∖ \{NAND\} = ∅$
• $\{AC^*\} ∖ \{NAND\} = ∅$
• $\{ACC^0\} ∖ \{NAND\} = ∅$
• $\{ACC^*\} ∖ \{NAND\} = ∅$
• $\{TC^0\} ∖ \{NAND\} = ∅$
• $\{TC^*\} ∖ \{NAND\} = ∅$

Seems too good to be true, doesn't it? Why stop there!

• $\{TM\} ∖ \{NAND\} = ∅$

Cool! But, what does that mean for...

• $\{NTM\} ∖ \{NAND\} = ∅$

.... we should be careful, we might rip a whole in the universe...

• $\{P\} ∖ \{NAND\} = ∅$

Whoa! Is there anything NAND can't do!? Thankfully, it's not that simple, because if it were I'm pretty sure someone would have pointed it out before now.

I am deeply curious if anyone can point me to a published proof that details why it can't be done, though. ;)

original question follows

A definition of $AC^0$ circuit complexity taken from Wikipedia:

A Boolean circuit with n input bits is a directed acyclic graph in which every node (usually called gates in this context) is either an input node of in-degree 0 labeled by one of the n input bits, an AND gate, an OR or a NOT gate.

The well known result regarding parity and $AC^0$, also taken from from Wikipedia:

The Boolean function PARITY, which is 1 if and only if the sum of its input bits is odd, does not lie in $AC^0$.

My question is: "Why is this considered to be a fundamentally important result?"

edit: From the comments, it is clear that the fundamental point / question is not being understood. Specifically: It is obviously possible to physically build bounded depth and polynomial size PARITY circuits- you need only open up a book on constructing CMOS circuits and look at how a XOR gate is physically constructed.

The fact that you can not build n input constant depth XOR / PARITY gates using only AND and OR gates is not doubted or disputed- that's obvious. Below, a link is given to a six transistor, THREE input XOR (i.e., PARITY) gate. This means it is trivially possible to physically build "at least" THREE input with constant depth of one XOR / PARITY gates.

The primary point is: The fact that you can not build constant depth XOR / PARITY gates using AND and OR gates DOES NOT imply that constant depth XOR / PARITY gates can not be built. The $AC^0$ PARITY proof proves something much weaker: that constant depth XOR / PARITY gates can not be built using just AND and OR gates. This is not the same thing as proving that constant depth XOR / PARITY gates can not be built, and it is a mistake to assume that they are.

If this distinction is still not clear to you, consider that a proof that constant depth XOR / PARITY gates can not be built using a constant depth / polynomial size number of transistors would not only be a far stronger result, but can also be trivially falsified because such constructions do, in fact, exist (links provided below).

end edit

If this question seems naive to you, then a better question to you might be "The definition of $AC^0$, with the restriction of using only AND ∧, OR ∨, and NOT ¬ gates, seems arbitrary. What is the fundamental basis for this restriction?"

If your first impulse to "What is the fundamental basis for this restriction?" is that "The primitives AND ∧, OR ∨, and NOT ¬ are functionally complete for all of the boolean nullinary, unary, and binary operators" then: beware of the flaming arrows.

As an example of why the $AC^0$ restriction of AND ∧, OR ∨, and NOT ¬ is arbitrary, consider that:

• The Apollo Guidance Computer, circa 1966, was built using approximately 4,100 3-input NOR ⊽ gates.
• The Cray-1, circa 1976, was built using approximately 200,000 4 and 5 input NAND ⊼ gates.

For circuit builders, the decision to use either NAND ⊼ or NOR ⊽ gates as the only primitive is so blatantly obvious that it doesn't need mentioning. If this does not seem blatantly obvious to you, then: beware of the incoming flaming arrows.

Restricting ourselves to 2 input AND ∧, 2 input OR ∨, and 1 input NOT ¬ gates it is possible to create:

• A 2 input XOR ⊻ gate using two AND ∧, one OR ∨, and one NOT ¬ gate.

Restricting ourselves to just a single, 2 input NAND ⊼ gate, it is possible to create:

• A 2 input AND ∧ gate using two NAND ⊼ gates.
• A 2 input OR ∨ gate using three NAND ⊼ gates.
• A 1 input NOT ¬ gate using one NAND ⊼ gate.

Using the above, it is possible to restate $AC^0$ in terms of NAND ⊼ gates and furthermore calculate that it takes a total of seven NAND ⊼ gates using the original two AND ∧, one OR ∨, and one NOT ¬ gate definition for XOR ⊻. However, it is also possible to build a XOR ⊻ gate using less NAND ⊼ gates:

• A 2 input XOR ⊻ gate using four NAND ⊼ gates.

The seven NAND ⊼ gate and four NAND ⊼ gate constructions for a 2 input XOR ⊻ gate are "logically identical", producing exactly the same output for the same inputs. The fact that we were able to reduce the number of gates by nearly 50% for an XOR ⊻ gate should immediately raise serious questions as to whether or not the definition of $AC^0$ is useful, or even meaningful.

To make matters worse, when one goes to actually build gates in CMOS, the basic primitive is the FET transistor. For example, the following are "common" transistor counts for most CMOS technologies:

• Four transistors for a 2 input NAND ⊼ gate.

Therefore, in CMOS, it is possible to physically build the "logically equivalent" 2 input XOR ⊻ gate using

• Seven physical 2 input NAND ⊼ gates. This would require a total of twenty eight transistors.
• Four physical 2 input NAND ⊼ gates. This would require a total of sixteen transistors.

However, "logically equivalent" does not imply "physically optimal":

• Six transistors for a 2 input XOR ⊻ gate. Depending on some pedantic details, four transistor constructions are possible.

Which leads me back to my original question: "Why is this [PARITY does not lie in $AC^0$] considered to be a fundamentally important result?"

Because, at least to me, the result has absolutely nothing to deal with reality. In fact, taken at face value, one would incorrectly assume that the result implies that it is fundamentally impossible to construct a 2 input XOR ⊻ gate using "just" six transistors (relative to the four transistors required for a 2 input NAND ⊼ gate).

To cast further doubt as to whether or not the PARITY result is meaningful, it implies that constructing a n input XOR ⊻ gate would require "significantly" (for some definition of significantly) more "gates". However, using three 2 input XOR ⊻ gates, it is clearly possible to construct a "logically equivalent" n input XOR ⊻ gate:

• 3 input XOR ⊻ gate using two 2 input XOR ⊻ gates, for a total transistor count of ~twelve transistors.
• 4 input XOR ⊻ gate using three 2 input XOR ⊻ gates, for a total transistor count of ~eighteen transistors.

The following paper gives a description of a 3 input XOR ⊻ gate using just six transistors.

The 3 input xor gate is provided here: http://ir.hit.edu.tw/dspace/bitstream/310993100/202/1/02-12高性能三輸入互斥或／反互斥或電路之設計.pdf

The following paper gives a description of a 4 input XOR ⊻ gate using just fourteen transistors, and the author specifically states "I am sure that smaller gates do exist, but their implementation is beyond the scope of my experience."

Am I mistaken, or does the $AC^0$ PARITY "proof" make the subtle and unstated assumptions:

• The only boolean primitives available are AND ∧, OR ∨, and NOT ¬.
• That the fact that AND ∧, OR ∨, and NOT ¬ are functionally complete for all of the boolean nullinary, unary, and binary operators, and therefore "logically equivalent" to different "boolean basis" formulations (i.e., either NAND ⊼ or NOR ⊽ basis).
• The AND ∧, OR ∨, and NOT ¬ basis is the "optimal" (for some definition and/or metric of "optimal") basis for the boolean domain actualization (i.e., AND ∧, OR ∨, and NOT ¬ is the "provably optimal" physical manifestation).
• That "logically equivalent" is sufficiently strong / closed over "provably optimal" (for some "loose and informal" definition for the purposes of our discussion/point).

... or have I missed something? Is there something "fundamentally compelling" about the decision to limit $AC^0$ to AND ∧, OR ∨, and NOT ¬? Or the fact that it is possible to physically construct n input XOR ⊻ gates using significantly less resources than what one would expect using the "proven $AC^0$ PARITY result"?

Answer 1

While I understand the question you are trying to ask, I find the presentation sub-optimal. This might just be me, but I find the tone of the question slightly condescending. I'm sure this is not what you meant to convey -- I'm just telling you how it comes across to me.

Anyway, I can try to answer some of your questions. Let me start with a pair of misconceptions:

• Misconception 1: PARITY not in AC0 says that "it is not possible to build polynomial-size constant-depth circuits to compute parity in the real world."

This is not true at all. The result claims exactly what it does: It is not possible to compute parity using a constant-depth polynomial-size circuit composed only of (and this is the important part) NOT gates, and unbounded fan-in AND and OR gates.

• Misconception 2: It is believed that just because AND, OR and NOT gates form a complete basis, AC0 is robust under changing these gates to any other gates.

As you pointed out, this is not true. If you used unbounded fan-in XOR gates, then obviously PARITY has a depth-1 circuit. The class which has unbounded fan-in XOR gates in addition to the usual NOT, AND and OR gates is called AC⁰[2]. AC0 is not robust under changing the gate set (unlike some other classes like NC0, where any complete basis will do the job). For example if we allow the MAJORITY gate in addition to the AND, OR and NOT gates, we get a class called TC0, which is much bigger than AC0.

An interesting question which arises, and which you have explicitly asked, is the following:

"The definition of AC0, with the restriction of using only AND ∧, OR ∨, and NOT ¬ gates, seems arbitrary. What is the fundamental basis for this restriction?"

This is a nice question. It also has a good answer. I don't think I can answer this satisfactorily myself, so I'll let someone else do it. I'll try answering it myself if no one else chooses to do so. But note that the answer is not "AC0 models real world circuits."

This question also immediately leads to the question "Why is this result interesting?" I'm not sure if this is what you meant to ask, but some good answers are given on the complexity theory blog.

So if we look at your your claimed "subtle and unstated" assumptions, you'll find that most of them are very clearly stated. For example, the fact that you can only use AND, OR and NOT is in the definition of AC0. I can't imagine anything being stated more explicitly than that!

Answer to revision 4

In revision 4 it seems like the question really is "Why don't we allow AC0 to have NAND gates also (because those are the gates used in real life by EE folks)?"

The answer is simple. Adding unbounded fan-in NAND gates to AC0 does not make AC0 more powerful. So you can interpret PARITY not in AC0 as saying that "PARITY cannot be computed by constant-depth circuits with unbounded fan-in AND, OR, NAND and NOT gates."

An unbounded fan-in NAND gate is just an unbounded fan-in AND gate with the output negated. So every NAND gate can be replaced by an AND gate and a NOT gate. Then, all the NOT gates can be pushed down to the inputs using standard techniques. At the end, the depth remains the same, and the size might increase by something like a factor of 4.

Answer 2

Below, a link is given to a six transistor, THREE input XOR (i.e., PARITY) gate. This means it is trivially possible to physically build "at least" THREE input with constant depth of one XOR / PARITY gates.

Unless I am completely misinterpreting these sentences, I think there may be some confusion in how "constant depth" is defined. First off, in circuit complexity, we deal in families of circuits, one circuit for each input size. So, when we say we can compute PARITY in some circuit model, what we mean is we have a sequence of circuits $C_1, C_2, C_3, \ldots$ such that $C_k$ computes the parity function on $k$ boolean inputs. The idea of constant depth is that there exists some $D$ such that each circuit $C_k$ has depth at most $D$ for all $k$, no matter how large. Similarly, "poly-size" implies that there is some polynomial $p(x)$ such that each circuit $C_k$ has no more than $p(k)$ gates.

Exhibiting an instance of a circuit that computes the parity function on 3 inputs does not really say anything about "constant depth" as it is defined in complexity theory. "Constant depth" is a property of the asymptotic behavior of your circuit family.

Answer 3

Regarding the choice of basis: all finite bases are (polynomially) equivalent. That means that if $C$ is a circuit over a finite base $B$ and $B'$ is any complete basis, then there is an equivalent circuit $C'$ over $B'$ of size at most $\alpha_1 |C|^{\alpha_2}$, where $\alpha_1,\alpha_2$ depend only on $B,B'$. This is proved for example in Reckhow's thesis (Section 5.3), though the result itself is due to Spira. What this means informally is that when we're doing circuit complexity, we don't really care whether the basis is NAND or AND, OR, NOT. (That's because in circuit complexity we often don't care about polynomial factors.) NAND was chosen because that's what can be implemented in hardware. AND, OR, NOT were chosen for historical reasons: that's what was used in logic (along with similar bases such as NOT, IMPLIES for which $\alpha_2 = 1$ both ways). Circuits with unlimited arity PARITY gates don't fall under this formalism, since the basis is infinite.

Regarding the importance of Håstad's result: This was the first non-trivial bound in circuit complexity. It is still one of the best bounds known for non-monotone models, along with the Razborov–Smolensky methods, and Razborov's slightly superlinear lower bound for switching networks. All other bounds rely on restrictions of the model, usually monotonicity.

Parity is computed in real life in an iterative fashion, using tables or simply by "deep" circuits (this concept is of course hard to define exactly, since constant depth is an asymptotic notion). That's a different model. Circuits considered in circuit complexity are good enough for the P vs. NP question (or rather, P/poly vs. NP). At the time, it seems that people thought that the methods developed for small complexity classes would scale up to polysize circuits, but this hope hasn't materialized. Nowadays it is a less presumptuous specialist area.