Difference between revisions of "Parity"
| Line 6: | Line 6: | ||
==Properties== | ==Properties== | ||
* Parity only depends on the number of ones and is therefore a [[Symmetric function|symmetric Boolean function]]. | * Parity only depends on the number of ones and is therefore a [[Symmetric function|symmetric Boolean function]]. | ||
| − | * The [[decision tree complexity]] of the | + | * The [[decision tree complexity]] of the parity function is <math>D(f)=n</math>. |
* 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. | * 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 form]]s have the maximal number of 2<sup> ''n'' − 1</sup> monomials of length ''n'' and all [[conjunctive normal form]]s have the maximal number of 2<sup> ''n'' − 1</sup> clauses of length ''n''. <ref> [[Ingo Wegener]], Randall J. Pruim, ''Complexity Theory'', 2005, {{isbn|3-540-21045-8}}, [https://books.google.com/books?id=u7DZSDSUYlQC&pg=PA261&lpg=PA261&dq=%22parity+function%22+H%C3%A5stad&source=bl&ots=HNQ-Jx67yy&sig=qOg_lAiE3JbqsDdQO0rrmgxJmDs&hl=en&ei=U9PjSfGYDYjaswOCkNysCQ&sa=X&oi=book_result&ct=result&resnum=3#PPA260,M1 p. 260]</ref> | * The ''n''-variable parity function and its negation are the only Boolean functions for which all [[disjunctive normal form]]s have the maximal number of 2<sup> ''n'' − 1</sup> monomials of length ''n'' and all [[conjunctive normal form]]s have the maximal number of 2<sup> ''n'' − 1</sup> clauses of length ''n''. <ref> [[Ingo Wegener]], Randall J. Pruim, ''Complexity Theory'', 2005, {{isbn|3-540-21045-8}}, [https://books.google.com/books?id=u7DZSDSUYlQC&pg=PA261&lpg=PA261&dq=%22parity+function%22+H%C3%A5stad&source=bl&ots=HNQ-Jx67yy&sig=qOg_lAiE3JbqsDdQO0rrmgxJmDs&hl=en&ei=U9PjSfGYDYjaswOCkNysCQ&sa=X&oi=book_result&ct=result&resnum=3#PPA260,M1 p. 260]</ref> | ||
Revision as of 15:34, 19 March 2022
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.
- The decision tree complexity of the parity function is [math]D(f)=n[/math].
- 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
