Majority function
Encyclopedia
In Boolean logic
, the majority function (also called the median operator) is a function
from n inputs to one output. The value of the operation is false when n/2 or more arguments are false, and true otherwise.
Alternatively, representing true values as 1 and false values as 0, we may use the formula
The "−1/2" in the formula serves to break ties in favor of zeros when n is even; a similar formula can be used for a function that breaks ties in favor of ones.
A major result in circuit complexity
asserts that this function cannot be computed by AC0 circuits
of subexponential size.
A majority gate is a logical gate used in circuit complexity
and other applications of Boolean circuits. A majority gate returns true if and only if more than 50% of its inputs are true.
For an arbitrary n there exists a monotone formula for majority of size O(n5.3) . This is proved using probabilistic method
. Thus, this formula is non-constructive. However, one can obtain an explicit formula for majority of polynomial size using a sorting network
of Ajtai
, Komlós
, and Szemerédi
.
An abstract system satisfying these as axioms is a median algebra
.
Boolean logic
Boolean algebra is a logical calculus of truth values, developed by George Boole in the 1840s. It resembles the algebra of real numbers, but with the numeric operations of multiplication xy, addition x + y, and negation −x replaced by the respective logical operations of...
, the majority function (also called the median operator) is a function
Function (mathematics)
In mathematics, a function associates one quantity, the argument of the function, also known as the input, with another quantity, the value of the function, also known as the output. A function assigns exactly one output to each input. The argument and the value may be real numbers, but they can...
from n inputs to one output. The value of the operation is false when n/2 or more arguments are false, and true otherwise.
Alternatively, representing true values as 1 and false values as 0, we may use the formula
The "−1/2" in the formula serves to break ties in favor of zeros when n is even; a similar formula can be used for a function that breaks ties in favor of ones.
A major result in circuit complexity
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 Boolean circuits that compute them....
asserts that this function cannot be computed by AC0 circuits
AC0
AC0 is a complexity class used in circuit complexity. It is the smallest class in the AC hierarchy, and consists of all families of circuits of depth O and polynomial size, with unlimited-fanin AND gates and OR gates....
of subexponential size.
A majority gate is a logical gate used in circuit complexity
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 Boolean circuits that compute them....
and other applications of Boolean circuits. A majority gate returns true if and only if more than 50% of its inputs are true.
Monotone formulae for majority
For n = 1 the median operator is just the unary identity operation x. For n = 3 the ternary median operator can be expressed using conjunction and disjunction as xy + yz + zx. Remarkably this expression denotes the same operation independently of whether the symbol + is interpreted as inclusive or or exclusive or.For an arbitrary n there exists a monotone formula for majority of size O(n5.3) . This is proved using probabilistic method
Probabilistic method
The probabilistic method is a nonconstructive method, primarily used in combinatorics and pioneered by Paul Erdős, for proving the existence of a prescribed kind of mathematical object. It works by showing that if one randomly chooses objects from a specified class, the probability that the...
. Thus, this formula is non-constructive. However, one can obtain an explicit formula for majority of polynomial size using a sorting network
Sorting network
A sorting network is an abstract mathematical model of a network of wires and comparator modules that is used to sort a sequence of numbers. Each comparator connects two wires and sorts the values by outputting the smaller value to one wire, and the larger to the other...
of Ajtai
Miklós Ajtai
Miklós Ajtai is a computer scientist at the IBM Almaden Research Center. In 2003 he received the Knuth Prize for his numerous contributions to the field, including a classic sorting network algorithm Miklós Ajtai (born 2 July 1946, Budapest, Hungary) is a computer scientist at the IBM Almaden...
, Komlós
János Komlós (mathematician)
János Komlós is a Hungarian-American mathematician, working in probability theory and discrete mathematics. He is a professor of mathematics at Rutgers University since 1988. He graduated from the Eötvös Loránd University, then became a fellow at the Mathematical Institute of the Hungarian Academy...
, and Szemerédi
Endre Szemerédi
Endre Szemerédi is a Hungarian mathematician, working in the field of combinatorics and theoretical computer science. He is the State of New Jersey Professor of computer science at Rutgers University since 1986...
.
Properties
Among the properties of the ternary median operator < x,y,z > are:- < x,y,y > = y
- < x,y,z > = < z,x,y >
- < x,y,z > = < x,z,y >
- < < x,w,y > ,w,z > = < x,w, < y,w,z > >
An abstract system satisfying these as axioms is a median algebra
Median algebra
In mathematics, a median algebra is a set with a ternary operation < x,y,z > satisfying a set of axioms which generalise the notion of median or majority function, as a Boolean function.The axioms are# < x,y,y > = y...
.
See also
- Boolean algebra (structure)
- Boolean algebras canonically definedBoolean algebras canonically definedBoolean algebra is a mathematically rich branch of abstract algebra. Just as group theory deals with groups, and linear algebra with vector spaces, Boolean algebras are models of the equational theory of the two values 0 and 1...
- Majority problem (cellular automaton)Majority problem (cellular automaton)The majority problem, or density classification task is the problem of finding one-dimensional cellular automaton rules that accurately perform majority voting.Using local transition rules, cells cannot know the total count of all the ones in system...