Difference between revisions of "Parity"
m |
m (Added some even / odd stuff, a todo.) |
||
| Line 1: | Line 1: | ||
== Definition == | == 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. | 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. | ||
| Line 7: | 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> | ||
* A constant-depth [[Boolean circuit]] must have exponential size in order to represent the parity function. <ref>Johan Håstad, [http://www.nada.kth.se/~johanh/thesis.pdf Computational limitations of small depth circuits], 1987.</ref> | * A constant-depth [[Boolean circuit]] must have exponential size in order to represent the parity function. <ref>Johan Håstad, [http://www.nada.kth.se/~johanh/thesis.pdf Computational limitations of small depth circuits], 1987.</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. | |
== References == | == References == | ||
<references/> | <references/> | ||
| − | [[Category:symmetric function]] [[Category:balanced function]] | + | [[Category:symmetric function]] [[Category:balanced function]] [[Category:even function]] [[Category:odd function]] |
Revision as of 14:23, 5 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]
- A constant-depth Boolean circuit must have exponential size in order to represent the parity function. [2]
- 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
- ↑ Johan Håstad, Computational limitations of small depth circuits, 1987.
