algorithm - 用多项式大小布尔表达式表达事实

Question

如果我有布尔变量 a_1、a_2、..、a_n。如何使用多项式大小布尔表达式来表达设置为 true 的布尔变量的数量大于一些 k 的事实？（指数很容易 - 只需编写 newton(n,k) 表达式）。

Answer 1

使用任何排序网络对布尔值进行排序。然后只取 (k+1)'th 排序位，这会给你结果。

由于排序网络的每个元素都代表一对逻辑运算，因此您可以将此网络解释为逻辑表达式。^{使用良好的排序网络，这将为您提供具有 O(N*log 2} (N)) 操作的表达式。

Answer 2

令 t[i][j] 表示其中的元素 a_1, .., a_i, j 设置为真。现在我们可以清楚地看到

    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、..、a_(i-1) 中有 j-1 个变量。这是多项式大小表达式（大约n*k 个变量 t[i][j]，对于每个表达式，就像我上面写的那样）。然后如果 t[n][k] 为真，我们得到 n 个变量中至少 k 个为真。

参考 Evgeny 的答案，要按排序顺序（首先为真，然后为假）获取变量，我们查看序列 t[n][1], t[n][2], .. t[n][n ]。