Majority function

From Wikipedia, the free 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 fewer arguments are false, and true otherwise. Alternatively, representing true values as 1 and false values as 0, we may use the formula

\operatorname{Majority} \left ( p_1,\dots,p_n \right ) = \left \lfloor \frac{1}{2} + \frac{\sum_{i=1}^n p_i - 1/2}{n} \right \rfloor.

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 at least 50% +1 of its inputs are true.

[edit] 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 ⊕.

[edit] References

  • Valiant, L. (1984), “Short monotone formulae for the majority function”, Journal of Algorithms 5: 363–366 .

[edit] See also