Complejidad de las variantes 3SAT

Question

Esta pregunta está motivada por mi a otra pregunta en la que he dicho al hecho de que tanto betweeness y No -Betweeness problemas son NP $ $ -Complete. En el primer problema hay un orden total de tal manera que la restricción betweeness de cada triple se aplica mientras que en el problema más tarde hay un orden total de tal manera que la restricción betweeness de cada triple se violó.

¿Cuál es la complejidad de la siguiente 3SAT variantes:?

3SAT_1 = {($ \ phi $): $ \ phi $ tiene una misión que hace que cada cláusula false}

3SAT_2 = {($ \ phi $): $ \ phi $ tiene una misión de tal manera que exactamente la mitad de las cláusulas son verdaderas y la otra mitad es falso}

Answer 1

3SAT_1 es fácil, y una variante de 3SAT_2 es ??NP-completo. Mi conjetura es que 3SAT_2 también es NP-completo. Actualización:. Mi suposición se demuestra a continuación

Let $ C = x \ lor y \ lor z $ sea un cláusula. A continuación, $ \ lnot C = \ lnot x \ tierra \ lnot y \ tierra \ lnot z $. Una asignación hace que cada cláusula de $ \ phi $ false si hace todas sus negaciones cierto. La conjunción de la negación de todas las cláusulas es sólo un gran conjunto. Una conjunción es satisfiable si y sólo si no contiene una variable y su negación. Así 3SAT_1 está en P (de hecho, es en CA $ ^ $ 0).

La variante de 3SAT_2 pregunta si $ \ phi $ tiene una misión que hace exactamente $ 8/9 $ de las cláusulas verdaderos. Esto está claramente en NP. Para reducir 3SAT a esta variante, tome la fórmula $ \ phi $, y para cada cláusula $ C $ en $ \ phi $ añadir las ocho cláusulas $$ (X_c \ lor y_C \ lor z_C) \ tierra \ cdots \ tierra (\ lnot X_c \ lor \ lnot y_C \ lor \ lnot z_C). $$ En cualquier asignación, exactamente a las siete de estos son correctos. En total tenemos $ 9 | \ phi | $ cláusulas. De los $ 8 | \ phi | $ que hemos añadido, exactamente $ 7 | \ phi | $ son siempre correctas. De ahí que $ \ phi $ es satisfiable si y sólo si en la nueva fórmula uno puede satisfacer exactamente $ 8 | \ phi |. $ Limitaciones, que son $ 8/9 $ de sus cláusulas

Actualización: Aquí se produce una reducción de 3SAT a sí 3SAT_2. Dada una fórmula $ \ phi $, considerar dos casos. El primer caso es cuando podemos falsificar todas las cláusulas de $ \ phi $ a la vez. Como se muestra arriba, en este caso cada variable aparece sólo positiva o negativamente solamente, y así establecer de manera apropiada, la fórmula es satisfiable. De lo contrario, agregue $ | \ phi | $ cláusulas de la forma $ x \ lor y \ lor z $, donde $ x, y, z $ son nuevas variables. En cualquier cesión o bien todos ellos están satisfechos, o todos no están satisfechos. Dado que las cláusulas originales no pueden ser todos falsificados a la vez (por supuesto), la nueva fórmula puede ser un medio satisfecho-si y sólo si el original es satisfiable.