La satisfacción (SAT) es el problema de determinar si existe una asignación variable que cumple una fórmula booleana dada.
Dada una instancia de SAT, me gustaría poder estimar lo difícil que será resolver la instancia. Una forma es ejecutar solucionadores existentes, pero ese tipo de derrota el propósito de estimar la dificultad. Una segunda forma podría ser buscar la relación de cláusulas a variables, como se hace...
Estoy usando un solucionador SAT para codificar un problema, y como parte de la instancia SAT, tengo variables booleanas donde se pretende que exactamente una de estas sea verdadera y el resto debería ser falso (A veces he visto esto descrito como una codificación
Sea una fórmula booleana que consta de los operadores habituales AND, OR y NOT y algunas variables. Me gustaría contar el número de asignaciones para satisfacer B . Es decir, quiero encontrar el número de asignaciones diferentes de valores de verdad a las variables de para las cuales asume un valor...
Lo que quiero hacer es convertir un problema matemático que tengo en un problema de satisfacción booleana (SAT) y luego resolverlo usando un solucionador SAT. Me pregunto si alguien conoce un manual, una guía o cualquier cosa que me ayude a convertir mi problema en una instancia SAT. Además,...
WalkSAT y GSAT son algoritmos de búsqueda locales bien conocidos y simples para resolver el problema de satisfacción booleana. El pseudocódigo para el algoritmo GSAT se copia de la pregunta Implementación del algoritmo GSAT: ¿cómo seleccionar qué literal voltear? y presentado a...
Recientemente encontré en un artículo [1] una versión simétrica especial de SAT llamada 2/2/4-SAT . Pero hay muchas variantes completas de , por ejemplo: MONOTONE NAE-3SAT , MONOTONE 1-IN-3-SAT , ...notario públicoNP\text{NP} Algunas otras variantes son manejables: - SAT , Planar-NAE- SAT ,...
El algoritmo GSAT es, en su mayor parte, directo: obtienes una fórmula en forma conjuntiva normal y cambias los literales de las cláusulas hasta que encuentres una solución que satisfaga la fórmula o alcances el límite max_tries / max_flips y no encuentres solución. Estoy implementando el...
¿Cómo puedo probar que la conversión de CNF a DNF es NP-Hard? No estoy pidiendo una respuesta, solo algunas sugerencias sobre cómo
Tengo un problema de decisión NP-completo. Dada una instancia del problema, me gustaría diseñar un algoritmo que genere SÍ, si el problema es factible, y, de lo contrario, NO. (Por supuesto, si el algoritmo no es óptimo, cometerá errores). No puedo encontrar ningún algoritmo de aproximación para...
Después del lanzamiento de la biblioteca AIGER para manejar gráficos e inversores en algún momento en 2006 (creo), se lanzaron algunos solucionadores SAT de circuito en 2006-2008, y en algunas carreras / competiciones SAT hubo pistas AIG. Sin embargo, desde entonces parece que el enfoque se ha...
Los solucionadores de SAT se están volviendo cada vez más eficientes en la resolución de grandes instancias y se están utilizando como back-end en varios contextos. Cada vez que uno quiere usarlos para resolver un problema en un dominio específico, tiene que encontrar una codificación ad-hoc que no...
Decimos que el lenguaje es denso si existe un polinomio p tal que | J c ∩ Σ n | ≤ p ( n ) para todo n ∈ N . En otras palabras, para cualquier longitud dada n sólo existen polinomialmente muchas palabras de longitud n que no están en J .J⊆Σ∗J⊆Σ∗J \subseteq \Sigma^{*}ppp|Jc∩Σn|≤p(n)|Jc∩Σn|≤p(n) |J^c...
Estoy tratando de entender una prueba de integridad de NP que parece girar en torno a SAT / 3CNF-SAT. Tal vez sea tarde, pero me temo que no puedo pensar en una fórmula 3CNF que no pueda satisfacerse (probablemente me falta algo obvio). ¿Me puede dar un ejemplo para tal
Entonces, como se sabe, el problema de decisión 0-1 de ILP es NP-completo. Mostrar que está en NP es fácil, y la reducción original fue de SAT; desde entonces, se ha demostrado que muchos otros problemas de NP-Complete tienen formulaciones de ILP (que funcionan como reducciones de esos problemas a...
Supongamos que se nos dan dos números y y que queremos encontrar para l \ le i, \, j \ le r .lllrrrmax(i⊕j)max(i⊕j)\max{(i\oplus j)}l≤i,j≤rl≤i,j≤rl\le i,\,j\le r El algoritmo ingenuo simplemente verifica todos los pares posibles; por ejemplo en ruby tendríamos: def max_xor(l, r) max = 0...
Planar 3SAT es NP-completo. Una instancia plana de 3SAT es una instancia de 3SAT para la cual el gráfico creado con las siguientes reglas es plano: agregue un vértice para cada yXyoXyox_iXyo¯Xyo¯\bar{x_i} agregue un vértice para cada cláusulaCjCjC_j añadir una ventaja para todos los par( xyo,...
Estoy seguro de que alguien ha pensado en esto antes o lo descartó de inmediato, pero ¿por qué la teoría de la dicotomía de Schaefer junto con el teorema de Mahaney sobre conjuntos dispersos no implican P = NP? Aquí está mi razonamiento: crear un lenguaje que sea igual a SAT intersectado por un...
El conocido problema SAT se define aquí como referencia. El problema DOUBLE-SAT se define como DOUBLE-SAT={⟨ϕ⟩∣ϕ has at least two satisfying assignments}DOUBLE-SAT={⟨ϕ⟩∣ϕ has at least two satisfying assignments}\qquad \mathsf{DOUBLE\text{-}SAT} = \{\langle\phi\rangle \mid \phi \text{ has at least...
¿Cuál es la complejidad de MIN-2-XOR-SATMIN-2-XOR-SAT\text{MIN-2-XOR-SAT} y MAX-2-XOR-SATMAX-2-XOR-SAT\text{MAX-2-XOR-SAT} ? ¿Están en P? ¿Son NP-hard? Para formalizar esto más precisamente, dejemos Φ ( x ) = ∧norteyoCyo,Φ(x)=∧inCi,\Phi\left(\mathbf x\right)={\huge\wedge}_{i}^{n}C_i, donde x =(...
Esta es probablemente una pregunta estúpida, pero simplemente no entiendo. En otra pregunta se les ocurrió el teorema de dicotomía de Schaefer . Para mí, parece que demuestra que cada problema de CSP está en P o en NP-completo, pero no en el medio. Dado que cada problema de NP puede transformarse...