Parity
Definition
The [math]n[/math]-variable parity function is the Boolean function [math]f:\{-1,1\}^n\to\{-1,1\}[/math] defined by [math]f(x)=x_1 \cdot x_2 \cdot \ldots \cdot x_n[/math]. In other words, [math]f(x)=1[/math] if and only if the number of ones in the vector [math]x\in\{-1,1\}^n[/math] is odd.
The name "parity" can also mean that the parity of only some [math]k[/math] of the [math]n[/math] bits is checked.
Properties
- Parity only depends on the number of ones and is therefore a symmetric Boolean function.
- Over [math]\{-1,1\}[/math], the representation of the parity function is exactly the monomial [math]x_1 x_2 \ldots x_n[/math]. Thus all of its Fourier mass rests on the highest level.
- The n-variable parity function and its negation are the only Boolean functions for which all disjunctive normal forms have the maximal number of 2 n − 1 monomials of length n and all conjunctive normal forms have the maximal number of 2 n − 1 clauses of length n. [1]
- Parity is not in AC0: A constant-depth Boolean circuit must have super-polynomial size in order to represent the parity function. [2] In fact, a circuit of depth [math]d[/math] must have size [math]\exp n^{\Theta (\frac{1}{d-1})}[/math] in order to exactly compute parity. This is tight: there exists a circuit of this size which computes parity. [3] [4]
- Parity over [math]n[/math] bits is odd when [math]n[/math] is odd, and even when [math]n[/math] is even.
- Parity has nearest neighbor complexity bounded by [math]NN(f) \geq n+1[/math]. It has the maximal Boolean nearest-neighbor complexity, [math]BNN(f) = 2^n[/math]. [6]
References
- ↑ Ingo Wegener, Randall J. Pruim, Complexity Theory, 2005, Template:Isbn, p. 260
- ↑ Furst, Saxe, and Sipser Parity, Circuits, and the Polynomial-Time Hierarchy, 1984.
- ↑ J. Håstad, Almost optimal lower bounds for small depth circuits, in Proceedings of the 18th Annual ACM Symposium on Theory of Computing, STOC ’86, New York, ACM, 1986, pp. 6–20.
- ↑ A. C-C. Yao, Separating the polynomial-time hierarchy by oracles , in Proceedings of the 26th Annual IEEE Symposium on Foundations of Computer Science, FOCS ’85, 1985, pp. 1–10
- ↑ J. Håstad, On the Correlation of Parity and Small-Depth Circuits, SIAM J. Comput., 43(5), 1699–1708.
- ↑ Péter Hajnal, Zhihao Liu, György Turán, Nearest neighbor representations of Boolean functions, Theorem 10, Proposition 3
