La complexité des variantes 3SAT

Question

Cette question est motivée par mon réponse à une autre question dans laquelle je l'ai dit le fait que les deux Betweeness et non les problèmes sont -Betweeness $ NP -complete $. Dans le premier problème il y a un ordre total tel que la contrainte de betweeness de chaque triple est appliquée alors que dans le problème plus tard il y a un ordre total tel que la contrainte de betweeness de chaque triple est violée.

Quelle est la complexité des variantes 3SAT suivantes:?

3SAT_1 = {($ \ phi $): $ \ phi $ a une mission qui fait de chaque clause false}

3SAT_2 = {($ \ phi $): $ \ phi $ a une mission telle qu'exactement la moitié des clauses sont vraies et l'autre moitié est faux}

Answer 1

3SAT_1 est facile, et une variante de 3SAT_2 est NP-complet. Je pense que 3SAT_2 est NP-complet. Mise à jour:. Je suppose prouvé ci-dessous

Soit $ C = x \ lor y \ lor z $ soit une clause. Alors $ \ lnot C = \ lnot x \ terre \ lnot y \ terre \ lnot z $. Une cession fait toute clause de $ \ phi faux $ si elle fait toutes leurs négations vrai. La conjonction de la négation de toutes les clauses est juste une grande conjonction. Une conjonction est satisfiable si et seulement si elle ne contient pas une variable et sa négation. Donc 3SAT_1 est en P (en fait, il est en CA $ ^ 0 $).

La variante de 3SAT_2 demande si $ \ phi $ a une mission qui fait exactement 8/9 $ $ des clauses vraies. Ceci est clairement dans NP. Pour réduire 3SAT cette variante, prendre la formule $ \ phi $, et pour chaque article $ C $ en $ \ phi $ ajouter les huit articles $$ (x_C \ lor y_C \ lor z_C) \ terre \ terre \ cdots (\ lnot x_C \ lor \ lnot y_C \ lor \ lnot z_C). $$ En toute cession, exactement sept d'entre eux sont corrects. Au total, nous avons 9 $ | \ phi | $ clauses. Sur les 8 $ | \ phi | $ que nous avons ajouté, exactement 7 $ | \ phi | $ sont toujours correctes. Par conséquent $ \ phi $ est satisfiable si et seulement si la nouvelle formule on peut satisfaire exactement 8 $ | \ phi |. $ Contraintes, qui sont 8/9 $ de ses clauses

Mise à jour: Voici une réduction de 3SAT à 3SAT_2 lui-même. Étant donné une formule $ \ phi $, considérer deux cas. Le premier cas est quand on peut falsifier toutes les clauses de $ \ phi $ à la fois. Comme indiqué plus haut, dans ce cas, chaque variable apparaît que positivement ou négativement que, et ainsi la mise de manière appropriée, la formule est satisfiable. Dans le cas contraire, ajouter $ | \ phi | $ clauses de la forme $ x \ lor y \ lor $ z, où $ x, y, z $ sont de nouvelles variables. Dans toute cession, soit tous ces éléments sont satisfaits, ou tous ne sont pas satisfaits. Étant donné que les clauses d'origine ne peuvent pas être toutes falsifiées à la fois (par hypothèse), la nouvelle formule peut être demi-satisfait si et seulement si l'original est satisfiable.