QUESTION: What is the minimum size formula that computes the PARITY function?
Definition. Boolean formula: some boolean variabes that you can combine with ANDs and ORs.
This is distinct from a circuit because you aren’t allowed to re-use values.
Theorem. There is an \(\mathcal{O}(n^{2})\) size formula for computing parity.
Proof. \[[x\oplus y \oplus z\oplus w = 0] = ([x\oplus y = 0] \land [z\oplus w = 0]) \lor ([x\oplus y = 1] \land [z\oplus w = 1]). \] So we should get the recurrence \[T(n) = 4T(n/2)+4\] or something which solves to \(O(n^{2}).\)
What follows is based on some notes I found online.
The point of this blog post is to prove a lower bound!Theorem. There is no boolean formula for XOR of size smaller than \(n^{2}\).
Proof.
We use the notion of a formal complexity measure, which is a function mapping formulas to \(\mathbb{R}\) satisfying the following properties:
- \(\mu(x_i),\mu(\overline{x_i}) = 1\).
- \(\mu(x\lor y) \le \mu(x)+\mu(y)\), \(\mu(x\land y) \le \mu(x)+\mu(y)\).
For \(A, B\subset \left\{ 0,1\right\}^{n}\) define \[H(A, B) = \left\{ (a, b)\in A \times B\; : \;\Delta(a, b)=1 \right\}\] where \(\Delta\) measures the hamming distance.
Define \[K_{A, B} = \frac{|H(A,B)|^{2}}{|A||B|}.\]
Khrapchenko’s measure: Let \(f: \left\{ 0,1\right\}^{n} \to \left\{ 0,1\right\}\) be a circuit. Then we define \[\mu(f) = \max{K_{A, B}: A\subset f^{-1}(0), B\subset f^{-1}(1)}\]
Turns out this is a formal complexity measure.
The key fact about formal complexity measures is that they provide lower bounds on the minimum size formula that computes a function.
For \(f\) being PARITY we can compute
\[\mu(f) \ge n^{2},\] by taking \(A,B\) to just be the entire pre-images of \(0,1\) respectively. Neat!
Too bad this can’t prove \(P\neq NP\).