Majority function

From Wikipedia, the free encyclopedia

You have new messages (last change).
It has been suggested that this article or section be merged with Majority gate. (Discuss)

The majority function is a logic function from n inputs to one output, defined as follows: If more inputs are TRUE than are FALSE, then the majority function returns TRUE. Otherwise, the function returns FALSE.

Representing TRUE as 1 and FALSE as 0 provides this alternate definition: \operatorname{Majority} \left ( p_1,...,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 FALSE.

A major result in circuit complexity asserts that this function cannot be computed by AC0 circuits of subexponential size.

Retrieved from "http://en.wikipedia.org../../../m/a/j/Majority_function.html"