Con la esperanza de mejorar mis conocimientos sobre la cuestión, ¿podría alguien esbozar las entradas y salidas del problema 3-SAT? También sería útil si pudiera expresar cómo este problema difiere en su estructura a los problemas SAT, 2-SAT o 4-SAT.
Respuestas
¿Demasiados anuncios?
Sardathrion
Puntos
71
Yo partiría de la pregunta de qué es el SAT en general. SAT es un problema de satisfacción - digamos que tienes una expresión booleana escrita usando sólo AND, OR, NOT, variables y paréntesis. El problema SAT es: dada la expresión, ¿hay alguna asignación de valores TRUE y FALSE a las variables que haga que toda la expresión sea verdadera?
Por ejemplo,
$x_{1} \wedge x_{2} \vee x_{3}$
Problema SAT para esta expresión booleana: ¿existen tales valores de $x_{1},x_{2},x_{3}$ que la expresión booleana dada es TRUE. La respuesta al problema SAT es sólo SÍ o NO. No nos importa cuáles son los valores de $x_{1},x_{2},x_{3}$ , sólo la existencia de tales valores.
Si esto está bien, vamos a ir más allá.
El problema SAT3 es un caso especial del problema SAT, donde la expresión booleana debe tener una forma muy estricta. Debe estar dividida en cláusulas, de manera que cada cláusula contenga tres literales.
Por ejemplo,
$(x_{1} \vee x_{2} \vee x_{3}) \wedge (x_{4}\vee x_{5} \vee x_{6})$
Esta expresión booleana en forma 3SAT, 2 cláusulas, cada cláusula contiene 3 literales. La pregunta es la misma, ¿hay tales valores de $x_{1}...x_{6}$ que la expresión booleana dada es TRUE.
Si no fue de ayuda. Yo aconsejaría a la mirada en la aplicación de SAT y 3SAT problema que cerca de su campo de estudio.
ariel
Puntos
169
Hay un montón de osos de peluche A, B, C, D y así sucesivamente que son rojos por un lado y azules por otro. (Tú eliges cómo colorearlos)
Y hay un montón de alienígenas de 3 brazos realmente largos. Cada alienígena agarra 3 manos de oso de peluche. (Una mano de oso de peluche puede ser agarrada por más de un alienígena).
3-SAT es el problema de si se pueden colorear los osos de peluche de tal manera que cada alienígena tenga al menos una mano azul.
user8269
Puntos
46
Empezar con un montón de variables $x_1,x_2,\dots$ que, en lugar de tomar valores reales, sólo toman valores del conjunto, $\{{{\rm true,\ false}\}}$ . Si $a,b$ son tales variables entonces $a\vee b$ es verdadera a menos que $a$ y $b$ son ambos falsos (piensa, "o"); $a\wedge b$ es verdadera sólo si ambos $a$ y $b$ son verdaderos (piensa en "y"); $-a$ es verdadera si y sólo si $a$ es falso (piense en "no").
Una cláusula es una disyunción de variables, es decir, algo de la forma $x_{i_1}\vee x_{i_2}\vee\cdots\vee x_{i_n}$ donde algunas de esas variables podrían ser negaciones de otras variables (es decir, una cláusula podría ser algo así como $x\vee-y\vee z$ ). Es fácil saber si una cláusula es satisfacible, es decir, si hay valores de las variables que la hacen verdadera.
El problema de la satisfabilidad es el siguiente: dada una colección (finita) de cláusulas, ¿hay una manera de asignar valores a las variables para que todas las cláusulas sean verdaderas?
3SAT es el caso en el que cada cláusula tiene exactamente 3 términos.
EDITAR (para incluir algo de información sobre el punto de estudiar 3SAT):
Si alguien te da una asignación de valores a las variables, es muy fácil comprobar si esa asignación hace que todas las cláusulas sean verdaderas; en otras palabras, puedes comprobar eficazmente cualquier supuesta solución.
Si alguien te pregunta si hay una forma de asignar valores a las variables para que todas las cláusulas sean verdaderas, entonces podrías simplemente probar todas las posibles asignaciones de valores, y comprobar cada una de ellas. Pero como hay dos posibles asignaciones a cada variable, hay $2^k$ posibles asignaciones de valores (donde $k$ es el número de variables), y esto crece muy rápidamente. La gran pregunta es si hay una forma más inteligente de hacer las cosas para poder resolver el problema en un número de pasos polinómico en el tamaño del problema, en lugar de los muchos pasos exponenciales del enfoque ingenuo.
Nadie lo sabe. Lo que sí se sabe es que si hay un algoritmo eficiente para resolver 3SAT, entonces hay un algoritmo eficiente para resolver TODOS los problemas para los que se pueden probar supuestas soluciones de forma eficiente.
