computability - 計算可能性: 節の数が制限された SAT 式

Question

SAT2016 を定義 = {\phi | \phi は、最大で 2016 句を含む CNF 式です}。P \neq NP を仮定すると、SAT2016 は NP 完全ですか?

各節のリテラルの数は制限されていないため、節の数が一定に制限されている式の充足可能性をチェックするための多項式時間アルゴリズムが存在するかどうかはすぐにはわかりません。

あなたのアイデアは大歓迎です。

Answer 1

SAT2016はPです。

式を満たすには、すべての句の少なくとも 1 つのリテラルに 1 を割り当てる必要があることに注意してください。各句には、多くても2nリテラルが含まれます。したがって、すべての句から 1 つのリテラルを選択する方法は最大で(2n)^2016です。式が満足できるかどうかを調べるには、(多くても)(2n)^2016可能性を繰り返し (すべての節から 1 つのリテラルを選択する) 必要があり、それぞれの可能性が有効かどうかを確認します。つまり、2016 のリテラル (各句から 1 つ) の選択ごとに、2016 のリテラルのうち 2 つがたまたま特定の変数とその否定であるかどうかを確認する必要があります。その場合は、次の 2016 リテラルの選択に進みます。もしあなたがすべてを通り抜けたなら、(2n)^2016すべての可能性に矛盾が含まれていることがわかった場合、その式は満足できないと結論付けます。

ほとんどの(2n)^2016可能性があり、特定の可能性のチェックには一定の時間がかかるため (2016 のリテラルのセットで可能なすべてのペアをループする必要があるため)、アルゴリズムの実行時間は の多項式ですn。