10変数のSAT満足度

Question

次の問題がNPC：

であることを証明しようとしています

$$ a={\ langle \ phi \ rangle \ \ big |\ \ \ \ \ text {はCNFであり、SATを持っています。任意10 varsがtrueの場合} \} $$

SATからの多項式マッピング削減を見つけようとしていますが、私は正確に10の変数を正確に課すよう強制する方法を見つけることができません。 私の考えは新しい式を作成することでした。私の考えに役立ちます。

助けを感謝します。

Answer 1

記載されている問題は $ p $ に含まれていますので、np-completeではありません。 $ | | \ Phi |= n $ では、変数の数は $ n $ より小さいため、 $ aのメンバーがわかります。$ は、10の真の割り当てを正確に持っています。そのため、ブルートフォースアルゴリズムによって、すべての可能な割り当てを変数に確認します。n、 $（^ {n} _ {10}）$ から10の変数を選択し、それらを $ true $ と他の変数を $ false $ に設定し、これが満足のいく割り当てであるかどうかを確認します。このアルゴリズムの実行時間は $（^ {n} _ {10}）* n= O（n ^ {11}）$ です。