Practical consequences of $Parity \notin AC^0$

Question

Background

Circuit complexity $AC^0$ is defined as the set of circuit families (i.e. sequences of circuits, one for each input size) of bounded depth and polynomial size built using unbounded fan-in AND, OR, and NOT.

The parity function $\oplus$ with $n$-bit input is equal to the XOR of the bits in the input.

One of the first circuit lowerbound proven in circuit complexity is the following:

[FSS81], [Ajt83]: $\oplus \notin AC^0$.

---

Questions:

Let $EC^0$ be the class of functions that can be computed using electronic circuits of bounded depth and polynomial size using electronic parts like transistors. (I made up the name $EC^0$, let me know if you know a better name for this).

1. Can we compute $\oplus$ in practice using $EC^0$ circuits?

2. What about unbounded fan-in AND/OR? Can we compute them in $EC^0$?

3. Does $\oplus \notin AC^0$ have any practical consequences? Is $AC^0$ important in practice?

4. Why is $\oplus \notin AC^0$ important for (theoretical) computer scientists?

---

Note:

This post contains interesting questions but OP seems to refuse to make the post more readable and fix the misconception in it for some reason, so I am reposting questions from it. (It would be easier to edit the original post but currently there isn't an agreement if it is OK to heavily edit another user's post.)

Related:

• Parity and $AC^0$

• Why is parity not in $AC^0$ important? (Computational Complexity Blog)

Answer 1

I am not an electrical engineer, but search for online patents regarding switching circuits for parity gates, and all proposals (I found patents only until the end of the 1970s) discuss the size-versus-depth problem. All three patents I have looked at propose solutions of logarithmic depth, based on fanin-2 gates. So the answer to your first question is possibly "no".

J.J. Moyer: Parity Check Switching Circuit, United States Patent US3011073, 1961

A.F. Bulver et al.: NAND Gate realization of the n-input parity function, United States Patent US3718904, 1973

P.J. Baun, Jr.: Parity Circuits, United States Patent US4251884, 1981

Answer 2

Johne, what is your problem? You're trying to argue about things no one ever claimed. No one said that the parity lower bound poses some fundamental limit to computing XOR with circuits other than those for which the theorem applies (i.e. AC^0 circuits). There are no hidden assumptions or veiled implications here. In particular we all know for example that it is possible to compute XOR with polynomial-sized NAND circuits of logarithmic depth, even with constant fan-in.

Shannon's quote is largely irrelevant too. There is no indication there that he even suspected that constant-depth AND-OR circuits need to have exponential size in order to compute Parity. Of course he might have guessed, since it is easy to conjecture this should be true after playing with the problem for a while, but so what?

You're missing entirely the point: proving lower bounds is exceedingly difficult, and we have to start somewhere, with the simplest models. This was essentially the first circuit lower bound, the techniques lead to many interesting ideas (including other fields such as learning theory), and although the result is plausible the proof is insightful and not at all trivial.

The fact that the result seems intuitive does not make it obvious; if you think it is, please provide a proof that parity is not in AC^0. Everyone knows that P is not equal to NP too for that matter, but nobody is anywhere near having a proof.

Your complaints in other threads about NAND gates make no sense either. This lower bound holds equally well for constant-depth circuits built up from NAND gates, as they're basically the same. Choosing to state the result with AND, OR, NOT is just a matter of convenience. So this may be a real-world application in terms you like: constant-depth circuits of NAND gates computing parity require exponential size. It does give a practical limitation, even if that's not the most important thing. It says that small XOR circuits for large number n of inputs must have either depth growing with n or gates other than NAND. Why aren't you satisfied with this?

Your claim that circuit depth is not an issue in the real world is also very misleading, since depth is directly related to time and the maximum frequency at which the clock can operate.

By the way, the CS community was well aware of the EE boolean circuit theory and built upon that, contrary to what you claim.

Answer 3

The follow link gives an overview of most CMOS gates. Note that "AND OR Inverted" (AOI) and "OR AND Inverted" (OAI) in the link. These circuits are typically a fraction of the size it would take to create the same circuit using their discrete components. For example, a OAI33 circuit (taken from a commercial foundries standard cell library) takes ~$1.62^2$ area, but building the same circuit using the equivalent discrete cells takes ~$3.82^2$ area.

• CMOS Technology Logic Circuit Structures

The following describes an eight transistor full adder circuit, which is typically defined in boolean algebra as $s = a \oplus b \oplus c_{in}$. For comparison, a typical 2 input {NAND, OR, XOR, etc} gate is typically composed of four to eight transistors.

• High Speed, Low Power 8T Full Adder Cell

A good place to find high speed, compact XOR / XNOR gates is in full-adders and Hamming ECC circuits (which are typically in the critical path).

Also, the issue of circuit depth is typically not a concern in VLSI synchronous logic. The only depth of any consequence is the critical path, which defines the maximum clock period. The vast majority of combinatorial logic propagate their results in a fraction of the time for the critical path. Critical paths tend to occur with some combinatorial logic that needs to pass through several areas scattered over a chip.

Many times it is possible to "pipeline" combinatorial logic to meet the timing constraints. This has the effect of creating a circuit that takes a new input and produces a new output every clock cycle, but has a latency of $n$ clock cycles before a given input is available on the output. This tends to make most circuits ~$O(1)$ in practice.

You may find the following paper of interest, which discusses VLSI $AT^2 = \Omega(n^2)$ complexity:

• On the Complexity of VLSI Implementations and Graph Representations of Boolean Functions with Application to Integer Multiplication

This is from the Computation Complexity Blog:

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?

To which the answer is: no, no one builds PARITY circuits in the real world this way. The last time anyone wanted to do this was when the only thing they had to work with was mechanical relays and this is why Shannons ~$2^n/n$ lower bound for most circuits result is for {AND, OR, NOT}. Even Shannon knew XOR could not be represented efficiently using just {AND, OR, NOT}:

It can be shown by a study of special cases that $\lambda(3) = 8$, the function

$X \oplus Y \oplus Z = X(YZ+Y'Z') + X'(YZ'+Y'Z)$

requiring eight elements in its most economical realization. $\mu(3)$, however, is actually 3. It seems probable that, in general, the function

$X_1 \oplus X_2 \oplus \ldots \oplus X_n$

requires $4(n-1)$ elements but no proof has been found.