algorithm - 事実を多項式サイズのブール式で表現する

Question

ブール変数 a_1、a_2、..、a_n があるとします。多項式サイズのブール式を使用して、true に設定されたブール変数の数が k より大きいという事実をどのように表現できますか? (指数関数は簡単です - newton(n,k) 式を書くだけです)。

Answer 1

任意のソート ネットワークでブール値をソートします。次に、(k + 1) 番目に並べ替えられたビットを取得するだけで、結果が得られます。

並べ替えネットワークの各要素は論理演算のペアを表すため、このネットワークを論理式として解釈できます。適切なソート ネットワークを使用すると、O(N*log ² (N)) 操作の式が得られます。

Answer 2

t [i] [j]は、要素a_1、..、a_i、jのうちの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、..、a_（i-1）にj-1個の変数があるため。これは多項式サイズ式です（約n*k変数t[i][j]、上記で書いたような式ごとに）次に、t [n] [k]が真の場合、少なくともk個のn個の変数が真であることがわかります。

Evgenyの回答を参照すると、変数を並べ替えられた順序（最初にtrue、次にfalse）で取得するために、シーケンスt [n] [1]、t [n] [2]、.. t[n][nを調べます。 ]。