用多项式大小布尔表达式表达事实
如果我有布尔变量 a_1, a_2, .. , a_n。如何使用多项式大小布尔表达式来表达设置为 true 的布尔变量数量大于某个 k 的事实？ （指数很容易 - 只需编写 newton(n,k) 表达式即可）。
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).
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
使用任何排序网络对布尔值进行排序。然后只需取第 (k+1) 位排序即可得到结果。
由于排序网络的每个元素代表一对逻辑运算，因此您可以将该网络解释为逻辑表达式。有了良好的排序网络，这将为您提供 O(N*log2(N)) 运算的表达式。
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*log2(N)) operations.
令 t[i][j] 表示元素中的 a_1, .., a_i, j 被设置为 true。
现在我们可以清楚地看到
（因为 a_1, .., a_(i-1) 中已经设置了变量，或者设置了 a_i 并且 a_1, .. , a_(i-1) 中有 j-1 个变量。
这是多项式大小表达式（围绕 n*k 个变量 t[i][j]，对于每个表达式，就像我上面写的那样）。然后，如果 t[n][k] 为真，我们就知道 n 个变量中至少 k 为真。
参考叶夫根尼的回答，
为了按排序顺序获取变量（首先是 true，然后是 false），我们查看序列
t[n][1]、t[n][2]、...t[n][n]。
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
(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].