Es ampliamente conocido que las fórmulas CNF se pueden dividir aproximadamente en 2 clases amplias: aleatoria versus estructurada. Las fórmulas estructuradas de CNF, en oposición a las fórmulas aleatorias de CNF, exhiben algún tipo de orden, mostrando patrones que es poco probable que ocurran por...
Lo que me pregunto específicamente es si existe una condición interesante en el porcentaje de asignaciones que satisfacen una fórmula 3SAT para garantizar que tales problemas sean manejables. Supongamos, por ejemplo, la clase de problemas 3SAT que de las 2 n asignaciones posibles satisfacen la...
Estoy considerando el lenguaje de todas las fórmulas lógicas proposicionales satisfactorias, SAT (para asegurarnos de que tenga un alfabeto finito, codificaríamos las letras proposicionales de alguna manera adecuada [editar: las respuestas señalaron que la respuesta a la pregunta puede no ser...
¿Cuáles son los obstáculos para hacer que los solucionadores SAT sean competitivos con algoritmos gráficos especializados? En otras palabras, ¿es factible esperar solucionadores de SAT que puedan reemplazar el rol de diseñador de algoritmos, es decir, poder reconocer automáticamente la estructura...
Sea un vector de variables booleanas. Sea dos circuitos booleanos en . Digamos que es similar a si:x=(x1,…,xn)x=(x1,…,xn)x=(x_1,\dots,x_n)C,DC,DC,DxxxCCCDDD Pr[C(x)≠D(x)]Pr[C(x)≠D(x)]\Pr[C(x) \ne D(x)] es exponencialmente pequeño, cuando xxx se dibuja uniformemente al azar desde...
Impagliazzo, Paturi y Calabro, Impagliazzo, Paturi introdujeron la hipótesis del tiempo exponencial (ETH) y la hipótesis del tiempo fuertemente exponencial (SETH). Aproximadamente, SETH dice que no existe un algoritmo que resuelva SAT en el tiempo . 1.99n1.99n1.99^n Me preguntaba qué significaría...
Este reciente artículo de FOCS2013, Strong Backdoors to Bounded Treewidth SAT de Gaspers y Szeider habla sobre el vínculo entre el ancho del árbol del gráfico de la cláusula SAT y la dureza de la instancia. Para instancias 3-SAT aleatorias, es decir, instancias 3-SAT elegidas al azar, ¿cuál es...
¿Existe un resultado conocido en la clase de complejidad 1-en-3-SAT con un número restringido de ocurrencias variables? Se me ocurrió la siguiente reducción parsimoniosa con Peter Nightingale, pero quiero citar algo si esto se sabe. Aquí está el truco que se nos ocurrió. Esto muestra que...
Todos los solucionadores de #SAT que conozco, por ejemplo, RelSat, C2D, solo devuelven el número de instancias satisfactorias. Pero quiero saber cada una de esas instancias? ¿Existe tal solucionador #SAT o cómo debo modificar un solucionador #SAT disponible para hacer
He estado desarrollando un algoritmo SAT durante un tiempo y he llegado a un punto en el que me gustaría compartirlo. No conozco a muchas personas en ciencias de la computación, y no estoy seguro exactamente a dónde acudir. Me pregunto qué recursos están disponibles para alguien con un algoritmo...
Estoy interesado en una variación SAT donde la fórmula CNF es monótona (no se niegan variables). Tal fórmula es obviamente satisfactoria. Pero digamos que el número de variables verdaderas es una medida de cuán buena es nuestra solución. Entonces tenemos el siguiente problema: MÍNIMO VERDADERO...
¿Es un problema CNF SAT NP difícil cuando el número total (pero no el ancho) de las cláusulas de 3 o más términos está limitado por una constante? ¿Qué pasa específicamente cuando solo hay una de esas
Estoy interesado en reducir -Clique a SAT sin hacer que la instancia sea mucho más grande.kkk Clique está en NP, por lo que puede reducirse a SAT utilizando espacio logarítmico. La reducción directa del libro de texto de Garey / Johnson explota la instancia a un tamaño cúbico . Sin embargo,...
Elberfeld, Jakoby y Tantau 2010 ( ECCC TR10-062 ) demostraron una versión eficiente del espacio del teorema de Bodlaender. Demostraron que para los gráficos con ancho de árbol como máximo , se puede encontrar una descomposición de árbol de ancho k usando espacio logarítmico. El factor constante en...
¿Cuál es la definición estándar de Planar 3-SAT? He visto varias definiciones diferentes. ¿Cuál fue el documento original que lo definió y demostró que era NP
¿Existe una clase natural de fórmulas de CNF, preferiblemente una que se haya estudiado previamente en la literatura, con las siguientes propiedades:CCC CCC es un caso fácil de SAT, como por ejemplo Horn o 2-CNF, es decir, la membresía en puede probarse en tiempo polinomial, y las fórmulas pueden...
Estoy interesado en instancias individuales "difíciles" de problemas NP-completos. Ryan Williams discutió el problema SAT0 en el blog de Richard Lipton . SAT0 pregunta si una instancia SAT tiene la solución específica que consiste en todos los 0. Esto me hizo pensar en construir instancias SAT que...
Me gustaría saber el estado actual de la transición de fase para k-sat aleatorio, dadas n variables y m cláusulas, cuál es la c = m / n más conocida para los límites superior e
Esta pregunta ha surgido en mi mente después de leer las contribuciones de András Salamon y Colin McQuillan a mi pregunta anterior Soluciones de conteo de fórmulas Monotone-2CNF . EDITAR 30 ª Mar 2011 pregunta Agregado n ° 2. EDITAR 29 º Oct 2010 Pregunta reformuló después de la propuesta...
Un idioma está en la clase D P si hay dos idiomas L 1 ∈ N P y L 2 ∈ c o N P de modo que L = L 1 ∩ L 2LLLDPDPDPL1∈NPL1∈NPL1 \in NPL2∈coNPL2∈coNPL2 \in coNPL=L1∩L2L=L1∩L2L = L1 \cap L2 Un problema canónico completo de es SAT-UNSAT: dadas dos expresiones 3-CNF, F y G , ¿es cierto que F es...