次の特殊な局所プロパティを持つ3SATインスタンスを考えます。ブール式にn個の変数があり、1,2,3 ... nという番号がつけられているとします。各節には、数が互いに+ -10以内にある変数が含まれています。このような3SATのインスタンスを解くための線形時間アルゴリズムを与える。線形3SAT：3SATの線形時間バージョン
私はこの問題を解決することができませんでしたが、私の直感は我々がグラフで問題をマップすることができれば、その後に解決することができるが、はるか遠くに行くことができなかったということです。..
これは、比較的直接的な動的プログラミングの問題です。どちらの境界についてもかなり簡単なインデックス作成の問題は無視して、解決策を説明します。
m番目のステップの後では、変数（m-10、m-9、...、m + 10）の可能な値のセットがあります。方程式1..mの解に至るすべての以前の変数について。
m + 1番目のステップでは、この可能な解集合の各メンバーを取り、m-10番目の値を無視し、m + 11番目の値についてそれぞれの可能性を考慮します。 m + 1番目の式が真の場合、その解パターンがまだ追加されていない場合にのみ、これを次の解集合に追加してヒストリをポイントします。
これは、m + 2ステップ目の準備です。
必要なn個のステップがあり、それぞれ約200万個の可能なケースが考えられるため、これは線形です。
（楽しい挑戦。ちょうど解決策を見つけられないために、しかし、がありますどのように多くのソリューションをカウントする。このアルゴリズムを変更します）
私はあなたがポリ時間内だけで強引にそれをすることができると思います。句リストを2つに分割します。分割の両側にある変数を網羅的に検索します。最大30個ありますので、2^30 = O（1）の設定を試してみてください。これらの変数が設定されると、再帰的に両辺を解くことができます。それぞれは、n/2変数を持つ独立したSATインスタンスです。
それは、分割の両側で一定数の変数が存在する理由を詳しく説明していただけます。 –
（x1 + x2 '+ x3）のようなものがあるとします。 （x1 '+ x2 + x3） （x4' + x5 + x6）| （x4 + x5 '+ x6） .......................... .............. ............ （x30 + x31 '+ x32）| （x30 + x31 + x32 '） 分割の各側に30以上の変数があります。 –
私は、分割の両側に現れる30個以下の変数があることを意味します。 –
それは、各ステップで20個の変数を試してみる必要があります。これは2^20個の可能なケースを試してみることを意味します！私は正しい？ –
説明したように、実際には2^21（0を忘れないでください）です。実際にはm-10番目の値を無視して2^20に戻すことはできますが、これは大きな定数ですが、定数であるため、アルゴリズムのbig-Oは変更されません。 – btilly