Difference between revisions of "Parity"
m (Improved parity-AC0 connections following comment by Roei Tell) |
m (Added approximation property) |
||
| Line 9: | Line 9: | ||
* 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 [[:CAtegory:AC0 function|AC0]]: 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 is not in [[:CAtegory:AC0 function|AC0]]: 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 [[:CAtegory:AC0 function|AC0]]: 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. | ||
Revision as of 05:58, 30 September 2018
Definition
TODO: extend the page to include parity of some specific [math]k[/math] bits out of the entire [math]n[/math].
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.
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.
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.
