3SAT único a 1-en-3sat único

Question

Supongamos que tengo una fórmula CNF con cláusulas de tamaño 2 y 3. Tiene una asignación satisfactoria única.

Se realizó a partir de un circuito de multiplicación binaria donde multiplicé dos números primos A y B de tal manera que A * B= S donde S es un número de semiprime. Añadí las condiciones que A!= 1, B!= 1 y A <= B, luego agregué el valor de S a la fórmula Asegúrese de que la asignación sea única. La única forma de satisfacer la fórmula es poner los valores de los primos A y B en el orden correcto en los bits de entrada.

En 1-IN-3SAT, forzamos que exactamente 1 literal debería ser cierto en cada triplete y otros dos falsos. Si exactamente 2 literales son verdaderos, podemos voltear todos los iterales en la cláusula para obtener una cláusula equivalente 1-en-3SAT (en otras palabras, 2 en-3SAT es el mismo problema).

Observación básica: Mientras que una cláusula regular o elimina 1 posibilidad de 8, una cláusula 1 en 3 elimina 5 posibilidades de 8.

3SAT se puede reducir a 1-IN-3 SAT, de modo que si la fórmula 3SAT es satisfactoria, entonces también la fórmula reducida.

Sin embargo, las reducciones no parecen preservar el número de tareas, introduciendo nuevas variables sin forzar su valor.

puede reducirse 3SAT únicos a 1-en-3sat ...

1. Sin saber la asignación correcta?
2. Si no, al saber la asignación correcta?

Answer 1

Sí, una fórmula 3-SAT $ \ phi $ se puede transformar en una fórmula SAT de 1 IN-3 $ \ PHI '$ mientras se preserva el número de asignaciones satisfactorias. Para evitar ambigüedades, usaré " $ \ vee $ " entre literales de una cláusula 3-SAT y comas entre literales de una cláusula SAT de 1 en-3. < / p>

---

Déjeme preliminarmente, mostrarle eso, dado dos literales $ A $ y $ b $ , podemos Simular un nuevo tipo de cláusula $ (x= a \ wedge b) $ que obliga al valor de una nueva variable $ x $ para ser $ a \ wedge b $ usando solo las restricciones de SAT 1-IN-3, sin introducir ninguna solución nueva.

Considerar las cluasas: $$ (\ Overline {B}, C, X) \ Wedge (a, c, d) \ wedge (\ Overline {A}, E, X) \ Wedge (b, e, f) $$

Si $ a=top $ , y $ b=top $ , luego el segundo y la cuarta cláusulas garantiza que $ c= d= e= f=bot $ . Las cláusulas de 1ª y 3ª se aseguran de que $ x=top $ .

Si $ a=top $ , y $ b=bot $ , luego el 2do La cláusula garantiza que $ c= d=bot $ . La primera cláusula entonces garantiza que $ x=bot $ . La tercera cláusula garantiza que $ e=top $ , y la cuarta cláusula implica $ f=bot $ .

El caso $ a=bot $ , y $ b=top $ es simétrico.

Si $ a=bot $ y $ b=bot $ , luego el 1º y Terceras cláusulas implican $ c= e= x=bot $ . Las cláusulas 2 y 4 se aseguran $ d= f=top $ .

---

Ahora estoy listo para transformar una fórmula $ \ phi $ de 3sat a una fórmula $ \ phi '$ < / SPAN> de 1-IN-3 SAT. Considere ahora una cláusula $ (a \ vee b \ vee c) $ de $ \ phi $ . Esto se puede transformar en las siguientes cláusulas SAT equivalentes 1 en 3:

• Agregar una nueva variable $ x $ que es verdadero IFF $ a $ es falso y $ b $ es verdadero. Esto está codificado por la cláusula $ (x=overline {a} \ wedge b) $ .

• Agregar una nueva variable $ y $ que es verdadero IFF $ a $ es falso , $ b $ es falso, y $ c $ es verdadero. Necesitaremos una variable adicional $ z $ . La cláusula $ (z=overline {a} \ wedge \ overline {b}) $ asegura que $ z $ < / span> es verdadero si y solo si $ a $ es falso y $ b $ es falso. Luego, el valor de $ y $ puede ser ejecutado por la cláusula $ (y= z \ wedge c) $ .

• Si $ (A \ vee b \ vee c) $ es verdadero, entonces al menos uno de $ Un $ , $ b $ , o $ c $ es verdadero. Esto significa que exactamente uno de $ a $ , $ x $ , y $ y $ es cierto. En el converso, si $ (A \ vee b \ vee c) $ es falso, luego en todo $ A $ , $ x $ , y $ y $ son falsos. Esto muestra que $ (A \ vee b \ vee c) $ es satisfactorio si y solo si $ (a, x, y $ ) es satisfecho.

Luego hemos construido una fórmula SAT de 1 IN-3 equivalente $ \ phi '$ que usa un superSet de las variables de la fórmula original de 3 SAT $ \ phi $ . Una tarea de verdad a las variables de $ \ phi '$ satisface $ \ phi' $ si y solo si La asignación restringida a las variables de $ \ phi $ satisface $ \ phi $ . Por lo tanto, si se introduce alguna solución nueva para $ \ phi '$ , debe ser debido a las variables recién agregadas $ x $

n>, $ y $ , y $ z $ (un set para cada cláusula).Sin embargo, los valores de estas variables están completamente determinadas por los valores de las variables de $ \ phi $ .

Answer 2

Dicha reducción se describe en el Apéndice B de Régis Barbankon, en un gráfico único 3-Colorabilidad y reducciones parsimonales en el plano .Barbanquon lo atribuye al trabajo anterior ([9] en la bibliografía).En otros lugares, he visto una atribución al famoso documento de Schaefer en el que demuestra su famoso teorema de dicotomía, entre lo contrario, dando una reducción de 3SAT a 1-IN-3SAT, que supuestamente es parsimonioso (no he comprobado).