多項式のサイズブール式で表現しています

ブール変数a_1、a_2、..、a_nを持っていれば、真に設定されているブール変数の数が、多項式のサイズブール式を使用して、いくつかのkよりも大きいという事実をどのように表現できますか？（指数関数は簡単です - ニュートン（n、k）式を書くだけです）。多項式のサイズブール式で表現しています

出典

2012-02-22 siemanko

ソートネットワークでブール値をソートします。次に、（k + 1）番目のソートされたビットを取ると、結果が得られます。

各ソートネットワークの要素は一対の論理演算を表しているため、このネットワークを論理式として解釈できます。良好なソートネットワークを使用すると、O（N * log （N））の演算式が得られます。

出典

2012-02-22 12:13:32

これだけです！私は、CNF（まだ多項式）でこの式が必要であることを特定できませんでした。ソート・ネットワークの例を考えてください。そうすれば、それを合理的に単純にすることができますか？ – siemanko

CNFはこの問題をはるかに困難にします。私はCNF表現を与えるソートネットワークを知らない。そして、私が知る限り、どの表現をCNFに変換すると、最悪の場合に指数関数的に爆発する可能性があります。私はCNFと多項式の両方の解を知らない。おそらくこれは不可能です。 –

さて、それは単に真実ではありません。人間が手にしたほとんどの展開はCNFに変換可能であり、すべてのチューリングマシンは多項式の複雑さでCNF表現として書くことができるので、ソートを行うマシンを使うと多項式の複雑さが増します。私が求めているのは、それが簡単で、手で書き出すことができる仕分けネットワークなので、証拠は簡単に保たれます。 – siemanko

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でJ-1の変数が存在している、...を、はっきりと見ることができますa（i-1）。これは多項式の大きさの表現である（上で書いたような各式のn * k変数t [i] [j]を中心に）。次にt [n] [k]が真、我々はn個の変数の少なくともkが真であることを取得します。

ソート順に変数を取得するにはエフゲニー答え、にReffering（最初trues、その後falses）、我々は、n [シーケンストンを見て] [1]、t [n] [2]、.. t [n] [n]。

出典

2012-02-23 15:52:57 siemanko

多項式のサイズブール式で表現しています

答えて

関連する問題