Difference between revisions of "Parity"
m (Improved parity-AC0 connections following comment by Roei Tell) |
m |
||
| (8 intermediate revisions by 2 users not shown) | |||
| Line 1: | Line 1: | ||
== Definition == | == 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 | + | The name "parity" can also mean that the parity of only some <math>k</math> of the <math>n</math> bits is checked. |
==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 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> | ||
| − | * Parity is not in [[ | + | * Parity is not in [[Circuit_complexity#AC0 | AC<sup>0</sup>]]: A constant-depth [[Boolean circuit]] must have super-polynomial size in order to represent the parity function. <ref>Furst, Saxe, and Sipser [https://wiki.epfl.ch/edicpublic/documents/Candidacy%20exam/Furst%20Saxe%20Sipser%20-%201984%20-%20Parity%20circuits%20and%20the%20polynomial-time%20hierarchy.pdf Parity, Circuits, and the Polynomial-Time Hierarchy], 1984.</ref> 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. <ref>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.</ref> <ref>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</ref> |
| + | ** Parity cannot even be approximated in [[Circuit_complexity#AC0 | AC<sup>0</sup>]]: A circuit of depth <math>d</math> and size <math>S</math> can only have a correlation of <math>2^{-c_d n / (\log S)^{d-1} }</math> with parity. <ref>J. Håstad, [https://epubs.siam.org/doi/10.1137/120897432 On the Correlation of Parity and Small-Depth Circuits], SIAM J. Comput., 43(5), 1699–1708.</ref> | ||
* Parity over <math>n</math> bits is [[:Category:odd function|odd]] when <math>n</math> is odd, and [[:Category:even function|even]] when <math>n</math> is even. | * Parity over <math>n</math> bits is [[:Category:odd function|odd]] when <math>n</math> is odd, and [[:Category:even function|even]] when <math>n</math> is even. | ||
| + | * Parity has [[nearest neighbor representation|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>. <ref>Péter Hajnal, Zhihao Liu, György Turán, [https://arxiv.org/pdf/2004.01741.pdf Nearest neighbor representations of Boolean functions], Theorem 10, Proposition 3</ref> | ||
== References == | == References == | ||
<references/> | <references/> | ||
| − | [[Category:symmetric function]] [[Category:balanced function]] [[Category:even function]] [[Category:odd function]] | + | [[Category:symmetric function]] [[Category:balanced function]] [[Category:evasive function]] [[Category:even function]] [[Category:odd function]] [[Category:Noise sensitive function]] |
Latest revision as of 10:02, 20 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
