Preguntas sobre programas de resolución para el problema de satisfacibilidad booleano.
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
¿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
Si tengo un problema difícil, un enfoque estándar es expresarlo como una instancia SAT e intentar ejecutar un solucionador SAT en él. Otro enfoque estándar es expresarlo como un problema de satisfacción de restricciones e intentar usar un solucionador CSP. Los dos se sienten de alguna manera...
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...
Estoy tratando de resolver un problema SAT de 25k cláusulas 5k variables. Como ha estado funcionando durante una hora (precosat) y me gustaría resolver los más grandes después, estoy buscando un SAT-Solver multinúcleo. Como parece haber muchos solucionadores SAT, estoy bastante perdido. ¿Alguien...
Los solucionadores de SAT modernos son muy buenos para resolver muchos ejemplos del mundo real de instancias de SAT. Sin embargo, sabemos cómo generar los difíciles: por ejemplo, use una reducción de factoring a SAT y proporcione los números RSA como entrada. Esto plantea la pregunta: ¿qué pasa si...
En el trabajo, se me ha encomendado la tarea de inferir cierta información sobre un lenguaje dinámico. Reescribo secuencias de declaraciones en letexpresiones anidadas , así: return x; Z => x var x; Z => let x = undefined in Z x = y; Z => let x = y in Z if x then T else F; Z => if x...
Leí en Wikipedia que la unificación es un proceso para resolver el problema de la satisfacción. Al mismo tiempo, sé que tales solucionadores se llaman "solucionadores SAT" o "solucionadores SMT". Entonces, ¿son nombres diferentes para la misma cosa? Si dice que son diferentes, señale una falla en...
Estoy tratando de enseñarme diferentes enfoques para la verificación de software. He leido algunos articulos. Hasta donde aprendí, la lógica proposicional con temporal generalmente usa la verificación de modelos con solucionadores SAT (en sistemas reactivos en curso), pero ¿qué pasa con la lógica...
En la página de Wikipedia aquí , describe bastante bien el algoritmo CDCL (y parece que las imágenes fueron tomadas de diapositivas creadas por Sharad Malik en Princeton). Sin embargo, al describir cómo dar marcha atrás, todo lo que dice es "al punto apropiado". MiniSAT también usa una variante del...
Imaginemos que tenemos una fórmula satisfactoria El problema a resolver es "¿Hay una asignación para las variables que hará F insatisfactorio? ". Una forma de resolver es encontrar todas las soluciones para F en términos de variables y si el recuento es < , la solución que falta será la...
Tengo la siguiente pregunta. ¿Los solucionadores SAT son deterministas? Me refiero, por ejemplo, al algoritmo miniSAT y DPLL . ¿Son completamente deterministas? Si estos algoritmos devolverán unSAT, ¿significa que ciertamente la solución no