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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
2
  • $\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
    Commented Nov 17, 2013 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. ♦
    Commented Nov 17, 2013 at 18:03

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.