I was reading a book about computational learning theory, and it said that this should be easily provable. I don't know if it is because of my insufficient background in complexity but I am struggling to prove this.
If the parity function is simply f = $x_1 \oplus x_2 \oplus x_3 \oplus… \oplus x_n$ , how do I prove this.
If i do a 2 input XOR, this is essentially a 5 gate circuit ($(\neg x_1 \wedge x_2) \vee (x_1 \wedge \neg x_2)$). I read somewhere that NOT gates are actually not considered when taking considering circuit complexity, is this true?
Best Answer
Since XOR is associative:
We can actually use $O(n)$ logic gates by using XOR sequentially: $$(\cdots(((x_1 \oplus x_2) \oplus x_3) \oplus x_4) \oplus \cdots$$
However if this is implemented naively as a circuit it takes $O(n)$ time since we need the value starting at $x_1$ to propagate.
It is much faster to use a binary tree structure: $$(\cdots((x_1 \oplus x_2) \oplus (x_3 \oplus x_4)) \oplus \cdots$$
This takes only $n-1$ XOR gates if $n$ is a power of $2$, so it is also $O(n)$ logic gates, but uses $O(\log n)$ time.
I don't know what the $O(n \log n)$ logic gate solution is intended to be.