A polynomial majority function

184 Views Asked by At

Let us introduce a boolean function $F(x_1,x_2,x_3,...,x_n)$, where $F=1$ when most of the variables $x_1,x_2,...,x_n$ are equal to $1$ and $F=0$ otherwise. This is called a majority function. The task is to construct an algorithm (a boolean formula) to calculate the function in the basis ($\land,\lor$) (meaning you can only use those two operators, no inversion operator) so that the complexity of the algorithm scales polynomially with $n$ (the amount of computations performed can be represented with a polynomial of $n$). Thank you in advance.