Expressing fact in polynomial size boolean expression

Question

If I have boolean variables a_1, a_2, .. , a_n. How can I express the fact that number of boolean variables which are set to true is bigger than some k, using polynomial size boolean expression? (Exponential is easy - just write newton(n,k) expressions).

Answer 1

Sort your booleans with any sorting network. Then just take (k+1)'th sorted bit, which gives you the result.

Since each of the sorting network's elements represents a pair of logical operations, you can interpret this network as logical expression. With good sorting network, this will give you an expression with O(N*log²(N)) operations.

Answer 2

let t[i][j] mean that out of elements a_1, .., a_i, j of them is set to true. Now we can clearly see that

    t[i][j] => (t[i-1][j] or (t[i-1][j-1] and a_i). 

(as either variable was already set in a_1, .., a_(i-1) or a_i is set and there is j-1 variables in a_1, .. , a_(i-1). This is polynomial size expression (around n*k variables t[i][j], for each one expression like the one I have written above). Then if t[n][k] is true, we get that our of n variables at least k is true.

Reffering to Evgeny answer, To get the variables in the sorted order (first trues, then falses), we look at the sequence t[n][1], t[n][2], .. t[n][n].