11
$\begingroup$

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:

$\endgroup$
9
  • $\begingroup$ $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. $\endgroup$
    – chazisop
    Dec 7, 2010 at 14:16
  • $\begingroup$ @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.) $\endgroup$
    – Kaveh
    Dec 7, 2010 at 14:41
  • $\begingroup$ 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. $\endgroup$
    – Aaron Roth
    Dec 7, 2010 at 15:19
  • $\begingroup$ @Aaron: I also don't remember much but I think loops were mainly for memory elements like flipflops and sequential systems. I don't think it is difficult to relate circuit complexity to logical/ digital 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. $\endgroup$
    – Kaveh
    Dec 7, 2010 at 16:10
  • 3
    $\begingroup$ @Tsuyoshi Ito: Thanks. I was just checking it on Wikipedia, it seems that one can easily implement unbounded AND and OR gates using linear number of NMOS. The structure of circuits are simple and does not change with the number of inputs to the gate. On the other hand, XOR circuit made from NMOS transistors seems more complicated, I don't know if scales well with increase in fan-in. $\endgroup$
    – Kaveh
    Dec 7, 2010 at 16:22

3 Answers 3

10
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Very interesting indeed. $\endgroup$ Dec 8, 2010 at 23:51
6
$\begingroup$

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.

$\endgroup$
1
  • 2
    $\begingroup$ 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 posted by him? (or to the meta discussion) Thanks in advance. $\endgroup$
    – Kaveh
    Dec 21, 2010 at 2:55
1
$\begingroup$

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.

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.

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:

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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Kaveh
    Dec 18, 2010 at 9:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.