次の特別な局所性プロパティを持つ 3SAT インスタンスを考えてみましょう。ブール式に n 個の変数があり、それぞれの句が互いに +-10 以内の変数を含むように、1、2、3....n の番号が付けられているとします。このような 3SAT のインスタンスを解くための線形時間アルゴリズムを与えてください。
私は問題を解決できませんでしたが、私の直感では、問題をグラフにマッピングできれば解決できるかもしれませんが、それ以上先には進めない..
1744 次
2 に答える
4
これは、比較的単純な動的計画法の問題です。いずれかの境界にまつわるかなり単純なインデックス作成の問題は無視して、解決策を説明します。
m 番目のステップの後、変数 (m-10、m-9、...、m+10) の可能な値のセットが得られます。これは、これまでの解である可能性があり、それぞれが以前のすべての変数の値のセットにリンクされています。これにより、方程式 1..m の解が得られます。
m+1 番目のステップでは、この可能なソリューション セットの各メンバーを取得し、m-10 番目の値を無視して、m+11 番目の値の各可能性を検討します。m+1 番目の方程式が真である場合、その解パターンがまだ追加されていない場合にのみ、これを次の解セットに追加し、履歴を指します。
これで、m+2 番目のステップの準備が整いました。
必要なステップは n 個あり、それぞれに約 200 万のケースが考えられるため、これは直線的です。
(楽しいチャレンジです。このアルゴリズムを変更して、解を見つけるだけでなく、解の数を数えるようにします。)
于 2012-04-18T17:06:33.330 に答える
1
ポリタイムでブルートフォースできると思います。句リストを 2 つに分割します。分割の両側にある変数の徹底的な検索。それらは最大で 30 個あるため、2^30 = O(1) の設定を試す必要があります。これらの変数が設定されると、両側を再帰的に解くことができます。それぞれが n/2 変数を持つ独立した SAT インスタンスです。
于 2012-04-18T16:54:27.917 に答える