¿Ha habido alguna investigación sobre

Una característica bien conocida de las instancias -SAT es la relación del número de cláusulas m sobre el número de variables n , es decir, el cociente ρ = m / n . Para cada k , hay un valor umbral α st \ para ρ ≪ α , la mayoría de las instancias son satisfactorias y para ρ ≫ α la mayoría de las instancias son insatisfactorias. Se han realizado muchas investigaciones para problemas donde ρ ≪ α y para problemas con ρ , k suficientemente pequeños$k$$m$$n$$\rho = m/n$$k$$\alpha$$\rho \ll \alpha$$\rho \gg \alpha$$\rho \ll \alpha$$\rho$$k$-SAT se vuelve solucionable en tiempo polinómico. Ver, por ejemplo, el artículo de la encuesta de Dimitris Achlioptas del Manual de Satisfabilidad ( PDF ).

Me pregunto si se ha realizado algún trabajo en la otra dirección (donde ), por ejemplo, si de alguna manera podemos transformar el problema de CNF a DNF en este caso para resolverlo rápidamente.$\rho \gg \alpha$

Entonces, esencialmente, ¿qué se sabe con respecto al SAT donde ?$\rho = m/n \gg \alpha$

Sí, ha habido Moshe Vardi recientemente dio una charla de encuesta en el taller de Fundamentos teóricos de BIRS sobre la solución de SAT aplicada :

• Moshe Vardi, Transiciones de fase y complejidad computacional , 2014.

(Moshe presenta la gráfica de su experimento un poco después del minuto 14:30 en su charla vinculada anteriormente).

Deje denotar la relación de la cláusula. A medida que el valor de ρ aumenta más allá del umbral, el problema se vuelve más fácil para los solucionadores de SAT existentes, pero no tan fácil como era antes de alcanzar el umbral. Hay un aumento muy fuerte en la dificultad a medida que nos acercamos al umbral desde abajo. Después del umbral, el problema se vuelve más fácil en comparación con el umbral, pero la disminución de la dificultad es mucho menos pronunciada.$\rho$$\rho$

Supongamos que denota la dificultad del problema wrt a n (en su experimento T ρ ( n ) es la mediana del tiempo de ejecución de GRASP en instancias 3SAT aleatorias con la relación de cláusula ρ ). Moshe sugiere que T ρ ( n ) cambia de la siguiente manera:$T_\rho(n)$$n$$T_\rho(n)$$\rho$$T_\rho(n)$

• el umbral: T ρ ( n ) es polinomial en n ,$\rho \ll$$T_\rho(n)$$n$
• está cerca del umbral: T ρ ( n ) es exponencial en n ,$\rho$$T_\rho(n)$$n$
• el umbral: T ρ ( n ) permanece exponencial en n pero el exponente disminuye a medida queaumenta ρ .$\rho \gg$$T_\rho(n)$$n$$\rho$

$k\text-\mathsf{SAT}$

• Para tales fórmulas, se han mostrado límites más bajos en la duración de las refutaciones en la resolución y sistemas de prueba proposicional más fuertes, comenzando con el documento " Muchos ejemplos difíciles para la resolución " de Chvátal y Szemerédi. Estos límites inferiores de resolución implican límites inferiores en el tiempo de ejecución de los solucionadores SAT basados ​​en DPLL y CDCL. Los límites inferiores más fuertes son para el cálculo polinómico, debido a Ben-Sasson e Impagliazzo .
• Para tales fórmulas, existen algoritmos deterministas eficientes para certificar la insatisfacción, es decir, algoritmos que generan "UNSAT" o "No sé", donde se requiere que la respuesta "UNSAT" sea correcta, y debe generar "UNSAT" en fórmulas insatisfactorias con alta probabilidad. Los mejores resultados en esa dirección se deben a Feige y Ofek .

Aquí hay un estudio / ángulo más antiguo pero relevante realizado por un experto líder.

• El límite del cuchillo de restricción Walsh 1998

$\kappa$

$\kappa$$\kappa$

$m/n \gg\alpha$