如果我有布尔变量a_1，a_2，a_n。如何使用多项式大小的布尔表达式来表达设置为true的布尔变量的数量大于某个k的事实？（指数很容易——只需编写牛顿（n，k）表达式即可）。
使用任何排序网络对布尔值进行排序。然后只取第（k+1）个排序的位，这就是结果。
由于排序网络的每个元素都表示一对逻辑运算，因此可以将该网络解释为逻辑表达式。有了良好的排序网络，这将给你一个O（N*log2（N））运算的表达式。
设t[i][j]表示元素a_1。。，其中的a_i，j被设置为true。现在我们可以清楚地看到
t[i][j] => (t[i-1][j] or (t[i-1][j-1] and a_i).
（因为变量已经设置在a_1，..，a_（i-1）中，或者设置了a_i，并且a_1、..中有j-1个变量，a_（i-1）。这是多项式大小的表达式（围绕n*k个变量t[i][j]，对于每一个表达式，就像我上面写的那样）。如果t[n][k]为真，则我们得到n个变量中至少k为真。
根据叶夫根尼的回答，为了获得排序顺序的变量（先是true，然后是false），我们查看序列t[n][1]，t[n][2]。。t[n][n]。