<p>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".</p>

<p>J.J. Moyer: Parity Check Switching Circuit, United States Patent US3011073, 1961</p>

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

<p>P.J. Baun, Jr.: Parity Circuits, United States Patent US4251884, 1981</p>

CC BY-SA 2.5
2010-12-08T23:51:21.523Z
Very interesting indeed.
Antonio E. Porreca
CC BY-SA 2.5
2010-12-07T21:09:24.833Z
2010-12-07T22:53:55.793Z
2010-12-07T22:53:55.793Z
Hermann Gruber
<p>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 <em>other than those for which the theorem applies</em> (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.</p>

<p>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?</p>

<p>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.</p>

<p>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.</p>

<p>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 <em>require</em> exponential size. It does give a practical limitation, even if that's not the most important thing. It says that small XOR circuits for <em>large</em> number n of inputs must have either depth growing with n or gates other than NAND. Why aren't you satisfied with this?</p>

<p>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.</p>

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

CC BY-SA 2.5
2010-12-21T02:55:25.810Z
thanks for the answer, but a large part of your answer is comments directed to johne and not to my questions. I understand that you have probably posted this as an answer because you cannot comment but I don't want this question turn into a discussion between you two, so could you please move the part of your answer which is directed at him to [the related question](http://cstheory.stackexchange.com/questions/3604/parity-and-circuit-complexity) posted by him? (or to [the meta discussion](http://meta.cstheory.stackexchange.com/questions/826/dealing-with-user-issue.)) Thanks in advance.
Kaveh
CC BY-SA 2.5
2010-12-21T02:16:46.733Z
2010-12-21T02:28:16.663Z
2010-12-21T02:28:16.663Z
david
<p>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.</p>

<ul>
<li><a href="http://people.bu.edu/rknepper/sc571/chapter5_ckts_A.ppt" rel="nofollow">CMOS Technology Logic Circuit Structures</a></li>
</ul>

<p>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.</p>

<ul>
<li><a href="http://www.wseas.us/e-library/conferences/2010/Cambridge/ICNVS/ICNVS-46.pdf" rel="nofollow">High Speed, Low Power 8T Full Adder Cell</a></li>
</ul>

<p>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).</p>

<p>Also, the issue of <em>circuit depth</em> is typically not a concern in VLSI synchronous logic.  The only <em>depth</em> 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.</p>

<p>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 <em>latency</em> of $n$ clock cycles before a given input is available on the output.  This tends to make most circuits ~$O(1)$ in practice.</p>

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

<ul>
<li><a href="http://www.computer.org/portal/web/csdl/doi/10.1109/12.73590" rel="nofollow">On the Complexity of VLSI Implementations and Graph Representations of Boolean Functions with Application to Integer Multiplication</a></li>
</ul>

<p>This is from the Computation Complexity Blog:</p>

<blockquote>
  <p>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?</p>
</blockquote>

<p>To which the answer is: <em>no</em>, 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}:</p>

<blockquote>
  <p>It can be shown by a study of special cases that $\lambda(3) = 8$, the function</p>
  
  <p>$X \oplus Y \oplus Z = X(YZ+Y'Z') + X'(YZ'+Y'Z)$</p>
  
  <p>requiring eight elements in its most economical realization. $\mu(3)$, however, is actually 3. It seems probable that, in general, the function </p>
  
  <p>$X_1 \oplus X_2 \oplus \ldots \oplus X_n$</p>
  
  <p>requires $4(n-1)$ elements but no proof has been found.</p>
</blockquote>

CC BY-SA 2.5
2010-12-18T09:48:25.613Z
Tahnks johne for the answer, but right now I am a little bit short of time but I will read your answer more carefully and look at the articles you have linked to when I find some free time. I have been talking with some friends form EE department also and have learned a few interesting things that I will post.
Kaveh
CC BY-SA 2.5
2010-12-18T08:44:02.283Z
2010-12-18T08:44:02.283Z
johne
<h3>Background</h3>
<p>Circuit complexity <span class="math-container">$AC^0$</span> is defined as the set of circuit families (i.e. sequences of circuits, one for each input size) of <em>bounded depth</em> and <em>polynomial size</em> built using <em>unbounded fan-in</em> AND, OR, and NOT.</p>
<p>The parity function <span class="math-container">$\oplus$</span> with <span class="math-container">$n$</span>-bit input is equal to the XOR of the bits in the input.</p>
<p>One of the first circuit lowerbound proven in circuit complexity is the following:</p>
<blockquote>
<p>[FSS81], [Ajt83]: <span class="math-container">$\oplus \notin AC^0$</span>.</p>
</blockquote>
<hr />
<h3>Questions:</h3>
<p>Let <span class="math-container">$EC^0$</span> be the class of functions that can be computed using <em>electronic</em> circuits of bounded depth and polynomial size using electronic parts like transistors. (I made up the name <span class="math-container">$EC^0$</span>, let me know if you know a better name for this).</p>
<blockquote>
<ol>
<li><p>Can we compute <span class="math-container">$\oplus$</span> in practice using <span class="math-container">$EC^0$</span> circuits?</p>
</li>
<li><p>What about unbounded fan-in AND/OR? Can we compute them in <span class="math-container">$EC^0$</span>?</p>
</li>
<li><p>Does <span class="math-container">$\oplus \notin AC^0$</span> have any practical consequences? Is <span class="math-container">$AC^0$</span> important in practice?</p>
</li>
<li><p>Why is <span class="math-container">$\oplus \notin AC^0$</span> important for (theoretical) computer scientists?</p>
</li>
</ol>
</blockquote>
<hr />
<h3>Note:</h3>
<p><a href="https://cstheory.stackexchange.com/questions/3604/parity-and-circuit-complexity">This post</a> 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.)</p>
<p>Related:</p>
<ul>
<li><p><a href="https://cstheory.stackexchange.com/questions/3154/parity-and-ac0">Parity and <span class="math-container">$AC^0$</span></a></p>
</li>
<li><p><a href="http://blog.computationalcomplexity.org/2008/03/why-is-parity-not-in-ac0-important.html" rel="nofollow noreferrer">Why is parity not in <span class="math-container">$AC^0$</span> important?</a> (Computational Complexity Blog)</p>
</li>
</ul>

CC BY-SA 2.5
2010-12-07T14:16:42.310Z
$NC^{0}$ is the family of BOOLEAN circuits like $AC^{0}$ but of bounded fan-in. I don't know much about circuit complexity, so I can't tell if electronic equals boolean. However, I know from computer architecture that all gates can be implemented using transistors. Since you have a bounded-fanin , I guess you have a bounded number of transistors too, so you are not violating the bounded depth and polynomial size.
chazisop
CC BY-SA 2.5
2010-12-07T14:41:31.843Z
@chazisop: All Boolean functions can be implemented using AND/OR/NOT, the point is if the implementation is of the required form, i.e. polynomially many parts and bounded depth. Note that $AC^0$ can alternatively be defined using fan-in 2 AND/OR gates, but the number of alternations of gates in the circuit should be bounded. (I might need to define more carefully what we mean by depth for an electronic circuit if it is not already defined in the literature.)
Kaveh
CC BY-SA 2.5
2010-12-07T15:19:13.027Z
From what I remember of my undergraduate architecture course (read: not much), actual circuits in your computer are not acyclic -- they have feedback loops and state, and are perhaps better modeled as finite automata. It seems to me that if there is a disconnect between results about $AC^0$ and results that can be applied to your laptop, this is the key distinction, rather than using transistors to implement your AND gates.
Aaron Roth
CC BY-SA 2.5
2010-12-07T16:10:51.053Z
@Aaron: I also don't remember much but I think loops were mainly for memory elements like [flipflops](http://en.wikipedia.org/wiki/Flip-flop_%28electronics%29) and sequential systems. I don't think it is difficult to relate circuit complexity to [logical](http://en.wikipedia.org/wiki/Logic_gate)/ [digital](http://en.wikipedia.org/wiki/Digital_electronics) circuits specially the combinatorial systems, the question is how to relate concepts like depth  and fan-in to electronic circuits made out of transistors. Maybe I should ask it on Physics.SE.
Kaveh
CC BY-SA 2.5
2010-12-07T16:18:39.847Z
I like the item 2 (What about unbounded fan-in AND/OR?  Can we compute them in EC0?).
Tsuyoshi Ito
CC BY-SA 2.5
2010-12-07T16:22:08.007Z
@Tsuyoshi Ito: Thanks. I was just checking it on Wikipedia, it seems that one can easily implement unbounded [AND](http://en.wikipedia.org/wiki/AND_Gate) and [OR](http://en.wikipedia.org/wiki/OR_Gate) gates using linear number of [NMOS](http://en.wikipedia.org/wiki/NMOS_logic). The structure of circuits are simple and does not change with the number of inputs to the gate. On the other hand, [XOR](http://en.wikipedia.org/wiki/XOR_gate) circuit made from NMOS transistors seems more complicated, I don't know if scales well with increase in fan-in.
Kaveh
CC BY-SA 2.5
2010-12-07T16:28:52.463Z
[continues] [NAND](http://en.wikipedia.org/wiki/NAND_gate) and [NOR](http://en.wikipedia.org/wiki/NOR_gate) also seem to be simple and scalable.
Kaveh
CC BY-SA 2.5
2010-12-07T17:11:54.690Z
Is it possible to get a more formal definition of $EC^0$? Exactly what kind of components are allowed under this computation model? How do they behave?
mhum
CC BY-SA 2.5
2010-12-07T20:39:42.953Z
@mhum: right now I don't have a good formal definition. These [combinatorial circuits](http://en.wikipedia.org/wiki/Combinational_logic) seem to be made mainly from basic [electronic parts](http://en.wikipedia.org/wiki/Electronic_circuits) like resistors and transistors; there are paths from VCC to ground; and wires for inputs and the output. Size is easy to define, but not sure about depth. I will try to ask EE people to see what measure of complexity they use in practice.
Kaveh
<cc.complexity-theory><circuit-complexity><physics><bounded-depth>
Practical consequences of $Parity \notin AC^0$
Kaveh
# Practical consequences of $Parity \notin AC^0$

(Asked by: username_0 on 2010-12-07)

### 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](https://cstheory.stackexchange.com/questions/3604/parity-and-circuit-complexity) 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$](https://cstheory.stackexchange.com/questions/3154/parity-and-ac0)
* [Why is parity not in $AC^0$ important?](http://blog.computationalcomplexity.org/2008/03/why-is-parity-not-in-ac0-important.html) (Computational Complexity Blog)

**Tags:** cc.complexity-theory, circuit-complexity, physics, bounded-depth

> **Comments:**
> **username_1**: $NC^{0}$ is the family of BOOLEAN circuits like $AC^{0}$ but of bounded fan-in. I don't know much about circuit complexity, so I can't tell if electronic equals boolean. However, I know from computer architecture that all gates can be implemented using transistors. Since you have a bounded-fanin , I guess you have a bounded number of transistors too, so you are not violating the bounded depth and polynomial size.  
> **username_0**: @username_1: All Boolean functions can be implemented using AND/OR/NOT, the point is if the implementation is of the required form, i.e. polynomially many parts and bounded depth. Note that $AC^0$ can alternatively be defined using fan-in 2 AND/OR gates, but the number of alternations of gates in the circuit should be bounded. (I might need to define more carefully what we mean by depth for an electronic circuit if it is not already defined in the literature.)  
> **username_2**: From what I remember of my undergraduate architecture course (read: not much), actual circuits in your computer are not acyclic -- they have feedback loops and state, and are perhaps better modeled as finite automata. It seems to me that if there is a disconnect between results about $AC^0$ and results that can be applied to your laptop, this is the key distinction, rather than using transistors to implement your AND gates.  
> **username_0**: @Aaron: I also don't remember much but I think loops were mainly for memory elements like [flipflops](http://en.wikipedia.org/wiki/Flip-flop_%28electronics%29) and sequential systems. I don't think it is difficult to relate circuit complexity to [logical](http://en.wikipedia.org/wiki/Logic_gate)/ [digital](http://en.wikipedia.org/wiki/Digital_electronics) circuits specially the combinatorial systems, the question is how to relate concepts like depth  and fan-in to electronic circuits made out of transistors. Maybe I should ask it on Physics.SE.  
> **username_3**: I like the item 2 (What about unbounded fan-in AND/OR?  Can we compute them in EC0?).  
> **username_0**: @username_3: Thanks. I was just checking it on Wikipedia, it seems that one can easily implement unbounded [AND](http://en.wikipedia.org/wiki/AND_Gate) and [OR](http://en.wikipedia.org/wiki/OR_Gate) gates using linear number of [NMOS](http://en.wikipedia.org/wiki/NMOS_logic). The structure of circuits are simple and does not change with the number of inputs to the gate. On the other hand, [XOR](http://en.wikipedia.org/wiki/XOR_gate) circuit made from NMOS transistors seems more complicated, I don't know if scales well with increase in fan-in.  
> **username_0**: [continues] [NAND](http://en.wikipedia.org/wiki/NAND_gate) and [NOR](http://en.wikipedia.org/wiki/NOR_gate) also seem to be simple and scalable.  
> **username_4**: Is it possible to get a more formal definition of $EC^0$? Exactly what kind of components are allowed under this computation model? How do they behave?  
> **username_0**: @username_4: right now I don't have a good formal definition. These [combinatorial circuits](http://en.wikipedia.org/wiki/Combinational_logic) seem to be made mainly from basic [electronic parts](http://en.wikipedia.org/wiki/Electronic_circuits) like resistors and transistors; there are paths from VCC to ground; and wires for inputs and the output. Size is easy to define, but not sure about depth. I will try to ask EE people to see what measure of complexity they use in practice.  

---

## 3 answers

### Answer by username_5 on 2010-12-07. Score: 10

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

> **Comments:**
> **username_6**: Very interesting indeed.  

---

### Answer by username_7 on 2010-12-21. Score: 6

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.

> **Comments:**
> **username_0**: thanks for the answer, but a large part of your answer is comments directed to username_8 and not to my questions. I understand that you have probably posted this as an answer because you cannot comment but I don't want this question turn into a discussion between you two, so could you please move the part of your answer which is directed at him to [the related question](http://cstheory.stackexchange.com/questions/3604/parity-and-circuit-complexity) posted by him? (or to [the meta discussion](http://meta.cstheory.stackexchange.com/questions/826/dealing-with-user-issue.)) Thanks in advance.  

---

### Answer by username_8 on 2010-12-18. Score: 1

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](http://people.bu.edu/rknepper/sc571/chapter5_ckts_A.ppt)

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](http://www.wseas.us/e-library/conferences/2010/Cambridge/ICNVS/ICNVS-46.pdf)

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](http://www.computer.org/portal/web/csdl/doi/10.1109/12.73590)

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.

> **Comments:**
> **username_0**: Tahnks username_8 for the answer, but right now I am a little bit short of time but I will read your answer more carefully and look at the articles you have linked to when I find some free time. I have been talking with some friends form EE department also and have learned a few interesting things that I will post.  

---

