3SATバリアントの複雑さ

Question

この質問は私によって動機付けられています 答え 私は、私が問題の間の問題と非継続的な問題の両方が$ np $ -completeであるという事実を述べた別の質問に。前者の問題では、各トリプルの間の制約が強制されるように合計順序がありますが、後の問題では、各トリプルの間の制約が違反するような合計順序があります。

次の3SATバリアントの複雑さは何ですか？：

3SAT_1 = {（$ phi $）：$ phi $には、すべての条項がfalseになる割り当てがあります}

3SAT_2 = {（$ phi $）：$ phi $には、節の正確な半分が真であり、残りの半分が虚偽であるような割り当てがあります}

Answer 1

3SAT_1は簡単で、3SAT_2のバリアントはNP不完全です。私の推測では、3SAT_2もNP不完全です。更新：私の推測は以下で証明されています。

$ c = x lor y lor z $とします。次に、$ lnot c = lnot x land lnot y land lnot z $。割り当ては、$ phi $のすべての句をすべての否定を真実にした場合に偽ります。すべての条項の否定の結合は、単なる大きな結合です。変数とその否定が含まれていない場合にのみ、接続詞は満足します。したがって、3SAT_1はPにあります（実際、AC $^0 $です）。

3SAT_2のバリアントは、$ phi $に条項の正確な$ 8/9 $を獲得する割り当てがあるかどうかを尋ねます。これは明らかにNPにあります。 3SATをこのバリアントに削減するには、式$ phi $を使用し、各節に対して$ phi $の$ c $を8つの条項$$（x_c lor y_c lor z_c） cdots land（ land（ lnot x_c lor lnot y_c lor lnot z_c）。合計で9ドル| phi | $ clausesがあります。追加した$ 8 | phi | $のうち、正確に$ 7 | phi | $は常に正しいです。したがって、新しいフォーミュラワンが正確に$ 8 | phi | $制約を満たすことができる場合にのみ、$ phi $は満たします。

更新：3SATから3SAT_2自体への削減です。式$ phi $が与えられた場合、2つのケースを検討してください。最初のケースは、すべての条項を$ phi $で一度に偽造できる場合です。上記のように、この場合、各変数は正にまたは否定的にのみ表示されるため、適切に設定すると、式は満足できます。それ以外の場合は、フォーム$ x lor y lor z $の$ | phi | $ clausesを追加します。ここで、$ x、y、z $は新しい変数です。割り当てでは、これらすべてが満たされるか、すべてが満たされていません。元の条項はすべて（仮定による）一度にすべて偽造することはできないため、元の式が満足できる場合にのみ、新しい式は半分に満足する可能性があります。