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) (Valiant 1984). 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.
Read more about this topic: Majority Function
Famous quotes containing the words formulae and/or majority:
“I don’t believe in providence and fate, as a technologist I am used to reckoning with the formulae of probability.”
—Max Frisch (1911–1991)
“There is but little virtue in the action of masses of men. When the majority shall at length vote for the abolition of slavery, it will be because they are indifferent to slavery, or because there is but little slavery left to be abolished by their vote. They will then be the only slaves. Only his vote can hasten the abolition of slavery who asserts his own freedom by his vote.”
—Henry David Thoreau (1817–1862)