CNF式では、SATにNP硬いのはどのようにいくつの句が必要ですか？

Question

変数と$ n $ 変数と定数の句を多項式で解くことができますので、CNF式のSATがわかりません。一方、 $ n $ 変数と $ o（n）を持つCNF式を見ることは難しくありません。 $ 句は、NP硬度に十分です（たとえば、3着色性のための固有式に関連するSATのインスタンスを考慮して、平面グラフに適用されます）。

これを正式に定義することは、 $ \ text {cnfsat} -f- \ text {clauses} $ 、関数 $ f $ 。変数が $ f（n）$ 句。これに基づいて、私たちが最も小さい関数 $ g $ が存在するようにが存在することです。 $ \ text {cnfsat} -f- \ text {clauses} $ がすでにnp-hard>の$ f \ f x 。 G= 1（定数の句数）が機能しないことを知っており、 $ g= n $ （線形数の節数）が機能します。

$ g=log n $ ？ $ o（\ lg \ lg n）$ 句を持つ式のためのCNFSATのための簡単なアルゴリズムはありますか？

Answer 1

下限。 $ g \ le c \ cdot \ sqrt {\ log n} $ 多項式-時刻アルゴリズムが存在する。アイデアは次のとおりです。いくつかの句が多すぎる変数が多すぎる場合は、変数が少ない句を傷つけずに、この句を満たすためにいくつかの変数を選択するのに些細なことであるべきです。次のように繰り返します。

変数の数を小さい句を見つけます。 $ x_1、\ ldots、x_k $ この句に参加している変数です。

• $ k> g $ の場合、式全体は満足です（私たちは1つずつ処理句を処理し、以前に選択しなかった変数を選択します）。
• それ以外の場合は、句を削除します。 $ x_1、\ ldots、x_k $ を削除します。

今、我々は削除された句を満たさなければなりません。 $ g $ 句があるので、それぞれが $ g $ 新しい変数を紹介します、これは、 $ g ^ 2= c ^ 2 \ cdot \ log n $ 変数全体であることを意味します。したがって、 $ n ^ {c ^ 2} $ 変数の組み合わせがあります、そして私たちは単なるブルートフォースを使用することができます。

条件付き上限。次の意味ではほぼ厳しいです。 $ n $ 変数と $ \ ge c \を as / strong> cdot n $ 句（ $ c $ の場合は、 $ 3 $ - 色調 $ \ alpha ^ n $ です（ $ \ alpha \ in（1,2] $ ）。私たちの変換後の同じ下限が保持されていることに注意してください（アルゴリズムの前に適用できるので）。したがって、少なくとも $ \ log ^ {1+ \ epsilon} nがある場合$ 句は、 $ \ fRAC {\ log ^ {1以降の\ epsilon} n} c $ 変数とランニング時間の下限を持つことができます。私たちの問題は

です

$$ \ alpha ^ {\ frac {\ log ^ {1+ \ epsilon} n} c}= n ^ {\ frac {\ log ^ \ epsilon n \ cdot \ log \ alpha} {c}}、$$

超多項式である