これは、始めるための宿題の質問です。始める前にいくつか質問があります。
私たちの問題は次のとおりです。
「次のように k-Independent Set から 2-SAT に還元します。n 個の頂点を持つグラフ G が n 個の命題から成り、頂点ごとに 1 つです。頂点 i が独立したセットに属している場合、頂点 i の各命題 xi は true に設定されます。すべてのエッジ (u,v) について、u と v の両方が独立集合に属することはできないという節を書きます。」
私の質問は、私が読んだものはすべて、2-SAT は NP 完全問題ではないということです。では、独立集合の問題からどのように削減できるのでしょうか?