文字通りが複数回発生しない3SATの制約付きバージョンが、多項式時間で解決可能であることを証明する方法は？

Question

私は課題を解決しようとしています（本から取られた アルゴリズム-S。Dasgupta、Ch Papadimitriou、およびUV Vazirani, 、第8章、問題8.6a）、そして私はそれが述べていることを言い換えています：

3SATは、各リテラルが最大2回表示される式に制限されている場合でもNPコンプリートのままであることを考えると、各リテラルが最大で1回表示される場合、問題は多項式時間で解決可能であることを示します。

句を複数のグループに分離することで、これを解決しようとしました。

1. 条項の残りの部分と共通の変数を持たなかった条項
2. 共通の変数が1つしかなかった条項
3. 共通の2つの変数がある条項
4. 共通の3つの変数すべてがある条項

私の推論は、そのようなグループの＃が有限であるという線に沿って試みられました（文字通りが複数回存在しないという制限が課されているため）。より少ない制限グループ（3、2、および1）になりますが、私はこれが私をどこにも連れて行くのではないことに気付きました。せいぜい2回、NP完全であることが証明されています。

ヒント/ソリューションをオンラインで検索してみましたが、得ることができるのは このリンク, 、述べられたヒントが私にとって十分に意味がなかったので、ここで逐語的に再現しています。

ヒント：各リテラルがせいぜい1回表示されるため、この問題を2SATの問題に変換します。したがって、リテラル$ X_I $が節$ c_j $に表示され、$ x_i $（すなわち、$ overline {x_i} $）の補数に表示される場合節$ c_k $で、新しい句節$ c_j lor overline {c_k} $を作成します。

$ c_j $と$ c_k $の両方にそれぞれ3つのリテラルがあります。$ c_j lor overline {c_k} $（または$ overline {c_j lor c_k}を実行することで2Satに変換する方法がわかりませんでした。 $間違って読んだら）。

ヒントを復号化すること、または私が探求できるパスを提供することの助けは本当に感謝しています。

Answer 1

一般性を失うことなく、各変数が肯定的かつ正確に一度否定的に1回表示されると想定できます（変数が値を設定して節を満たして節を削除すると、変数のみが表示される場合）。また、変数が句に複数回表示されないと仮定することもできます（変数が句で正と負の両方で表示される場合、句は満たされ、削除される可能性があります）。これらは満足度を変えません。

次に使用します 解決ルール 変数を1つずつ排除するために（各変数は正確に一度に一度見られ、一度負になるため、これは決定論的なプロセスです）。いつでも空の句を取得した場合、条項のセットは満足できません。そうでなければ満足します。それの訳は：

• 解決は完全な命題証明システムです（つまり、句が条項のセットによって論理的に暗示されている場合、解決ルールのみを使用して条項のセットから派生可能です）、

• 条項のセットは、論理的に空の句を意味する場合、満足できないものです。

このアルゴリズムは、各変数が正確に1回解決されるため、多項式時間がかかります。特に、解像度の各適用により、条項の総数が1つ減少するため、条項の数は増加しません。たとえば、解像度を$（x lor b） land（ overline {x} lor c） land dots）$に適用解決前より。対照的に、これを各リテラルの外観の数に制限なしで3SAT式に適用した場合、解像度を適用すると、条項の数が指数関数的に増加する可能性があります。