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, quiero resolver esto en un tiempo mejor que exponencial. Espero que un SAT Solver me ayude.
algorithms
reductions
satisfiability
Dchris
fuente
fuente
Respuestas:
El Capítulo 2 del Manual SAT (por Steven Prestwich) cubre cómo convertir los problemas de decisión discreta en CNF, con cierta profundidad. (Desafortunadamente, no creo que haya una versión borrador en línea; probablemente sea mejor consultar su biblioteca local). Varias de las otras referencias citadas en la peculiar descripción de Magnus Björk Las técnicas de codificación SAT exitosas también son útiles.
Si sus problemas son continuos, o si está especialmente interesado en los sistemas de desigualdades, entonces es más probable que otros tipos de solucionadores sean útiles. Como señala Kyle, los solucionadores SMT (como Z3 , Yices u OpenSMT ) pueden ser útiles, aunque tradicionalmente las teorías SMT tienden a centrarse en la verificación de software de computadora, por lo que los solucionadores SMT generalmente tienen un gran soporte para cosas como expresiones que involucran intervalos de enteros , pero puede funcionar mal en restricciones de inyectividad. Para los problemas que se expresan naturalmente como sistemas de desigualdades, CPLEX es el que hay que superar (solía estar disponible para uso académico de forma gratuita, y aún podría estarlo). Para algunos problemas de decisión combinatoria (como encontrarempaquetamientos de rectángulos en un cuadrado ), los solucionadores de restricciones como Minion superan a los solucionadores SAT y, a menudo, son más fáciles de usar.
fuente
A menos que esté traduciendo problemas matemáticos a instancias SAT como un ejercicio de aprendizaje, su tiempo se gastará mucho más fructíferamente aprendiendo sobre teorías de módulos de satisfacción . SMT le permitirá expresar ecuaciones y otras restricciones mucho más naturalmente que como instancias booleanas de SAT. Algunos solucionadores SMT admiten cuantificadores existenciales y universales, lo que le permite ir más allá de NP y expresar problemas PSPACE.
Además de ser más expresivos, los solucionadores SMT son más rápidos. No P = NP más rápido, pero más eficiente en que un buen solucionador SMT no descarta información estructural específica de la teoría que ayuda a guiar al solucionador a través del espacio de búsqueda. Hacer una reducción de Karp directamente a una instancia de SAT obliga al solucionador de SAT a volver a aprender toda esa estructura, a menudo a un costo exponencial. Por ejemplo, el hecho de que la suma es conmutativa se pierde tanto en los solucionadores SAT basados en DPLL como en la búsqueda local; ¡El solucionador no es consciente de que se trata de números en absoluto! Para evitar probar todas las permutaciones de x + y + z = 10, un solucionador SAT necesita un código de ruptura de simetría, que requiere la detección del automorfismo gráfico. Los mejores algoritmos actuales de reconocimiento de automorfismos de gráficos requieren un tiempo exponencial al número de vértices en el peor de los casos,
fuente
Dos herramientas que convierten lenguajes de alto nivel a SMT o CNF.
CVC La sintaxis está cerca de CAS.
CBMC Convierte un programa C a CNF, permitiendo afirmaciones. Las aserciones son siempre verdaderas o si son falsas se encuentra una entrada de contraejemplo. CBMC desenrolla bucles, por lo que ciertos programas C tienen CNF / SMT exponencialmente grandes.
fuente