Parity function

In Boolean algebra, a parity function is a Boolean function whose value is 1 if and only if the input vector has an odd number of ones. The parity function of two inputs is also known as the XOR function.

The parity function is notable for its role in theoretical investigation of circuit complexity of Boolean functions.

The output of the Parity Function is the Parity bit.

Contents

• 
  1 Definition
  


• 
  2 Properties
  


• 
  3 Computational complexity
  


• 
  4 Infinite version
  


• 
  5 See also
  


• 
  6 References
  

Definition

The n{displaystyle n}-variable parity function is the Boolean function f:{0,1}n→{0,1}{displaystyle f:{0,1}^{n}to {0,1}} with the property that f(x)=1{displaystyle f(x)=1} if and only if the number of ones in the vector x∈{0,1}n{displaystyle xin {0,1}^{n}} is odd.
In other words, f{displaystyle f} is defined as follows:

f(x)=x1⊕x2⊕⋯⊕xn{displaystyle f(x)=x_{1}oplus x_{2}oplus dots oplus x_{n}}.

Properties

Parity only depends on the number of ones and is therefore a symmetric Boolean function.

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 − 1monomials of length n and all conjunctive normal forms have the maximal number of 2 ^n − 1 clauses of length n.^[1]

Computational complexity

Some of the earliest work in computational complexity was 1961 bound of Bella Subbotovskaya showing the size of a Boolean formula computing parity must be at least O(n3/2){displaystyle O(n^{3/2})}. This work uses the method of random restrictions. This exponent of 3/2{displaystyle 3/2} has been increased through careful analysis to 1.63{displaystyle 1.63} by Paterson and Zwick (1993) and then to 2{displaystyle 2} by Håstad (1998). ^[2]

In the early 1980s, Merrick Furst, James Saxe and Michael Sipser^[3] and independently Miklós Ajtai^[4] established super-polynomial lower bounds on the size of constant-depth Boolean circuits for the parity function, i.e., they showed that polynomial-size constant-depth circuits cannot compute the parity function. Similar results were also established for the majority, multiplication and transitive closure functions, by reduction from the parity function.^[3]

Håstad (1987) established tight exponential lower bounds on the size of constant-depth Boolean circuits for the parity function. Håstad's Switching Lemma is the key technical tool used for these lower bounds and Johan Håstad was awarded the Gödel Prize for this work in 1994.
The precise result is that depth-k circuits with AND, OR, and NOT gates require size exp⁡(Ω(n1k−1)){displaystyle exp(Omega (n^{frac {1}{k-1}}))} to compute the parity function.
This is asymptotically almost optimal as there are depth-k circuits computing parity which have size exp⁡(O(n1k−1)t){displaystyle exp(O(n^{frac {1}{k-1}})t)}.

Infinite version

An infinite parity function is a function f:{0,1}ω→{0,1}{displaystyle fcolon {0,1}^{omega }to {0,1}} mapping every infinite binary string to 0 or 1, having the following property: if w{displaystyle w} and v{displaystyle v} are infinite binary strings differing only on finite number of coordinates then f(w)=f(v){displaystyle f(w)=f(v)} if and only if w{displaystyle w} and v{displaystyle v} differ on even number of coordinates.

Assuming axiom of choice it can be easily proved that parity functions exist and there are 2c{displaystyle 2^{mathfrak {c}}} many of them - as many as the number of all functions from {0,1}ω{displaystyle {0,1}^{omega }} to {0,1}{displaystyle {0,1}}. It is enough to take one representative per equivalence class of relation ≈{displaystyle approx } defined as follows: w≈v{displaystyle wapprox v} if w{displaystyle w} and v{displaystyle v} differ at finite number of coordinates. Having such representatives, we can map all of them to 0; the rest of f{displaystyle f} values are deducted unambiguously.

Infinite parity functions are often used in theoretical Computer Science and Set Theory because of their simple definition and - on the other hand - their descriptive complexity. For example, it can be shown that an inverse image f−1[0]{displaystyle f^{-1}[0]} is a non-Borel set.

See also

Related topics

• Error Correction


• Error Detection

The output of the function

• Parity bit

References

.mw-parser-output .refbegin{font-size:90%;margin-bottom:0.5em}.mw-parser-output .refbegin-hanging-indents>ul{list-style-type:none;margin-left:0}.mw-parser-output .refbegin-hanging-indents>ul>li,.mw-parser-output .refbegin-hanging-indents>dl>dd{margin-left:0;padding-left:3.2em;text-indent:-3.2em;list-style:none}.mw-parser-output .refbegin-100{font-size:100%}

1. 
   ^ Ingo Wegener, Randall J. Pruim, Complexity Theory, 2005, .mw-parser-output cite.citation{font-style:inherit}.mw-parser-output .citation q{quotes:"""""""'""'"}.mw-parser-output .citation .cs1-lock-free a{background:url("//upload.wikimedia.org/wikipedia/commons/thumb/6/65/Lock-green.svg/9px-Lock-green.svg.png")no-repeat;background-position:right .1em center}.mw-parser-output .citation .cs1-lock-limited a,.mw-parser-output .citation .cs1-lock-registration a{background:url("//upload.wikimedia.org/wikipedia/commons/thumb/d/d6/Lock-gray-alt-2.svg/9px-Lock-gray-alt-2.svg.png")no-repeat;background-position:right .1em center}.mw-parser-output .citation .cs1-lock-subscription a{background:url("//upload.wikimedia.org/wikipedia/commons/thumb/a/aa/Lock-red-alt-2.svg/9px-Lock-red-alt-2.svg.png")no-repeat;background-position:right .1em center}.mw-parser-output .cs1-subscription,.mw-parser-output .cs1-registration{color:#555}.mw-parser-output .cs1-subscription span,.mw-parser-output .cs1-registration span{border-bottom:1px dotted;cursor:help}.mw-parser-output .cs1-ws-icon a{background:url("//upload.wikimedia.org/wikipedia/commons/thumb/4/4c/Wikisource-logo.svg/12px-Wikisource-logo.svg.png")no-repeat;background-position:right .1em center}.mw-parser-output code.cs1-code{color:inherit;background:inherit;border:inherit;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;font-size:100%}.mw-parser-output .cs1-visible-error{font-size:100%}.mw-parser-output .cs1-maint{display:none;color:#33aa33;margin-left:0.3em}.mw-parser-output .cs1-subscription,.mw-parser-output .cs1-registration,.mw-parser-output .cs1-format{font-size:95%}.mw-parser-output .cs1-kern-left,.mw-parser-output .cs1-kern-wl-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right,.mw-parser-output .cs1-kern-wl-right{padding-right:0.2em}
   ISBN 3-540-21045-8, p. 260
   


2. 
   ^ Jukna, Stasys (Jan 6, 2012). Boolean Function Complexity: Advances and Frontiers. Springer Science & Business Media. pp. 167–173. ISBN 978-3642245084.
   


3. 
   ^ ^ab Merrick Furst, James Saxe and Michael Sipser, "Parity, Circuits, and the Polynomial-Time Hierarchy", Annu. Intl. Symp. Found.Coimputer Sci., 1981, Theory of Computing Systems, vol. 17, no. 1, 1984, pp. 13–27, doi:10.1007/BF01744431
   


4. 
   ^ Miklós Ajtai, "Σ11{displaystyle Sigma _{1}^{1}}-Formulae on Finite Structures", Annals of Pure and Applied Logic, 24 (1983) 1–48.
   

• 
  Håstad, Johan (1987), Computational limitations of small depth circuits (PDF), Ph.D. thesis, Massachusetts Institute of Technology.
  

This page is only for reference, If you need detailed information, please check here