In
Boolean algebra
In mathematics and mathematical logic, Boolean algebra is a branch of algebra. It differs from elementary algebra in two ways. First, the values of the variables are the truth values ''true'' and ''false'', usually denoted 1 and 0, whereas in e ...
, a parity function is a
Boolean function
In mathematics, a Boolean function is a function whose arguments and result assume values from a two-element set (usually , or ). Alternative names are switching function, used especially in older computer science literature, and truth function ( ...
whose value is one
if and only if
In logic and related fields such as mathematics and philosophy, "if and only if" (shortened as "iff") is a biconditional logical connective between statements, where either both statements are true or both are false.
The connective is bicondi ...
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
In theoretical computer science, circuit complexity is a branch of computational complexity theory in which Boolean functions are classified according to the size or depth of the Boolean circuits that compute them. A related notion is the circui ...
of Boolean functions.
The output of the parity function is the
parity bit
A parity bit, or check bit, is a bit added to a string of binary code. Parity bits are a simple form of error detecting code. Parity bits are generally applied to the smallest units of a communication protocol, typically 8-bit octets (bytes) ...
.
Definition
The
-variable parity function is the
Boolean function
In mathematics, a Boolean function is a function whose arguments and result assume values from a two-element set (usually , or ). Alternative names are switching function, used especially in older computer science literature, and truth function ( ...
with the property that
if and only if
In logic and related fields such as mathematics and philosophy, "if and only if" (shortened as "iff") is a biconditional logical connective between statements, where either both statements are true or both are false.
The connective is bicondi ...
the number of ones in the vector
is odd.
In other words,
is defined as follows:
:
where
denotes
exclusive or
Exclusive or or exclusive disjunction is a logical operation that is true if and only if its arguments differ (one is true, the other is false).
It is symbolized by the prefix operator J and by the infix operators XOR ( or ), EOR, EXOR, , ...
.
Properties
Parity only depends on the number of ones and is therefore a
symmetric Boolean function In mathematics, a symmetric Boolean function is a Boolean function whose value does not depend on the order of its input bits, i.e., it depends only on the number of ones (or zeros) in the input.Ingo Wegener, "The Complexity of Symmetric Boolean F ...
.
The ''n''-variable parity function and its negation are the only Boolean functions for which all
disjunctive normal form
In boolean logic, a disjunctive normal form (DNF) is a canonical normal form of a logical formula consisting of a disjunction of conjunctions; it can also be described as an OR of ANDs, a sum of products, or (in philosophical logic) a ''cluster c ...
s have the maximal number of 2
''n'' − 1 monomial
In mathematics, a monomial is, roughly speaking, a polynomial which has only one term. Two definitions of a monomial may be encountered:
# A monomial, also called power product, is a product of powers of variables with nonnegative integer expone ...
s of length ''n'' and all
conjunctive normal form
In Boolean logic, a formula is in conjunctive normal form (CNF) or clausal normal form if it is a conjunction of one or more clauses, where a clause is a disjunction of literals; otherwise put, it is a product of sums or an AND of ORs. As a can ...
s have the maximal number of 2
''n'' − 1 clauses of length ''n''.
[ ]Ingo Wegener
Ingo Wegener (December 4, 1950 in Bremen – November 26, 2008 in Bielefeld) was an influential German computer scientist working in the field of theoretical computer science.
Education and career
Wegener was educated at the Bielefeld University. ...
, Randall J. Pruim, ''Complexity Theory'', 2005,
p. 260
/ref>
Computational complexity
Some of the earliest work in computational complexity was 1961 bound of Bella Subbotovskaya
Bella Abramovna Subbotovskaya (17 December 1937 – 23 September 1982) was a Soviet mathematician who founded the short-lived Jewish People's University (1978–1983) in Moscow. Szpiro, G. (2007),Bella Abramovna Subbotovskaya and the Jewish Peop ...
showing the size of a Boolean formula computing parity must be at least . This work uses the method of random restrictions. This exponent of has been increased through careful analysis to by Paterson and Zwick (1993) and then to by Håstad (1998).
In the early 1980s, Merrick Furst, James Saxe
James is a common English language surname and given name:
*James (name), the typically masculine first name James
* James (surname), various people with the last name James
James or James City may also refer to:
People
* King James (disambiguati ...
and Michael Sipser
Michael Fredric Sipser (born September 17, 1954) is an American theoretical computer scientist who has made early contributions to computational complexity theory. He is a professor of applied mathematics and was the Dean of Science at the Massa ...
[Merrick Furst, James Saxe and Michael Sipser, "Parity, Circuits, and the Polynomial-Time Hierarchy", Annu. Intl. Symp. Found.Computer Sci., 1981, '']Theory of Computing Systems
''Theory of Computing Systems'' is a peer-reviewed scientific journal published by Springer Verlag.
Published since 1967 as ''Mathematical Systems Theory'' and since volume 30 in 1997 under its current title, it is devoted to publishing origi ...
'', vol. 17, no. 1, 1984, pp. 13–27, and independently Miklós Ajtai
Miklós Ajtai (born 2 July 1946) is a computer scientist at the IBM Almaden Research Center, United States. In 2003, he received the Knuth Prize for his numerous contributions to the field, including a classic sorting network algorithm (deve ...
[Miklós Ajtai, "-Formulae on Finite Structures", '' Annals of Pure and Applied Logic'', 24 (1983) 1–48.] established super-polynomial lower bound
In mathematics, particularly in order theory, an upper bound or majorant of a subset of some preordered set is an element of that is greater than or equal to every element of .
Dually, a lower bound or minorant of is defined to be an eleme ...
s on the size of constant-depth Boolean circuits
In computational complexity theory and circuit complexity, a Boolean circuit is a mathematical model for combinational digital logic circuits. A formal language can be decided by a family of Boolean circuits, one circuit for each possible input ...
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.[
established tight exponential lower bounds on the size of constant-depth ]Boolean circuits
In computational complexity theory and circuit complexity, a Boolean circuit is a mathematical model for combinational digital logic circuits. A formal language can be decided by a family of Boolean circuits, one circuit for each possible input ...
for the parity function. Håstad's Switching Lemma In computational complexity theory, Håstad's switching lemma is a key tool for proving lower bounds on the size of constant-depth Boolean circuits.
Using the switching lemma, showed that Boolean circuits of depth ''k'' in which only AND, OR, and N ...
is the key technical tool used for these lower bounds and Johan Håstad
Johan Torkel Håstad (; born 19 November 1960) is a Swedish theoretical computer scientist most known for his work on computational complexity theory. He was the recipient of the Gödel Prize in 1994 and 2011 and the ACM Doctoral Dissertation ...
was awarded the Gödel Prize
The Gödel Prize is an annual prize for outstanding papers in the area of theoretical computer science, given jointly by the European Association for Theoretical Computer Science (EATCS) and the Association for Computing Machinery Special Interes ...
for this work in 1994.
The precise result is that depth- circuits with AND, OR, and NOT gates require size to compute the parity function.
This is asymptotically almost optimal as there are depth- circuits computing parity which have size .
Infinite version
An infinite parity function is a function mapping every infinite binary string to 0 or 1, having the following property: if and are infinite binary strings differing only on finite number of coordinates then if and only if and differ on even number of coordinates.
Assuming axiom of choice
In mathematics, the axiom of choice, or AC, is an axiom of set theory equivalent to the statement that ''a Cartesian product of a collection of non-empty sets is non-empty''. Informally put, the axiom of choice says that given any collection ...
it can be easily proved that parity functions exist and there are many of them - as many as the number of all functions from to . It is enough to take one representative per equivalence class of relation defined as follows: if and differ at finite number of coordinates. Having such representatives, we can map all of them to 0; the rest of 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