2
$\begingroup$

Sipser example 9.29

He says: "one way to do so (compute the parity function with O(n) gates. One way to do so is build a binary tree that computes the XOR function, where the XOR function is the same as parity on 2 variables, and then implement each XOR gate with two NOTs and two ANDs, and one OR. ... Let A be the language of strings that contain an odd number of 1's. Then A has circuit complexity O(n)."

I'm not seeing the steps that lead to saying that A has circuit complexity of O(n). Why can we say that if we implement a binary tree of XORs we can compute the parity with O(n) gates?

$\endgroup$
2
$\begingroup$

Because the parity is 1 if and only if the XOR of all the bits is 1. In other words, computing the parity is equivalent to computing the XOR of the bits. Sipser describes how to compute the XOR of the $n$ bits with $O(n)$ gates, which means that this same circuit computes the parity of those $n$ bits with $O(n)$ gates.

$\endgroup$
  • $\begingroup$ "Sipser describes how to compute the XOR of the n bits with O(n) gates". Where? If he did that, this would be an trivial problem to answer. So I would like to know where he did that. $\endgroup$ – lars Nov 17 '13 at 4:50
  • $\begingroup$ @lars, you quoted it in your question. You build a binary tree that computes the XOR function. The binary tree has $n$ leaves, one leaf per input, and each internal node in the tree is an XOR gate. The root of the tree holds the output. There are $n$ leaves and $O(n)$ internal nodes, so a total of $O(n)$ XOR gates. The part you excluded also explains that each XOR gate can be implemented with $O(1)$ NOT/OR/AND gates, so in total, it takes $O(1) \times O(n) = O(n)$ gates to compute the XOR of the $n$ bits. $\endgroup$ – D.W. Nov 17 '13 at 18:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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