Considere el problema 3-SAT en n variables. El número de posibles cláusulas distintas es:
El número de instancias problema es el número de todos los subconjuntos del conjunto de posibles cláusulas: . Trivialmente, para cada , existen al menos una instancia satisfactoria y una instancia no satisfactoria. ¿Es posible calcular, o al menos estimar, el número de instancias satisfactorias para cualquier n dado? n ≥ 3
cc.complexity-theory
sat
Antonio Valerio Miceli-Barone
fuente
fuente
Respuestas:
Una larga historia de trabajo sobre las transiciones de fase en SAT ha demostrado que para cualquier fijo , hay un umbral parametrizado por la relación de número de cláusulas a que decide la satisfacción. Hablando en términos generales, si la proporción es menor a 4.2, entonces con una probabilidad abrumadora la instancia es satisfactoria (y por lo tanto, una gran fracción del número de instancias con estas muchas cláusulas y variables es satisfactoria). Si la proporción está ligeramente por encima de 4.2, entonces lo contrario se cumple, una fracción abrumadora de instancias no es satisfactoria.nnorte norte
Las referencias son demasiadas para citarlas aquí: una fuente de información es el libro de Mezard y Montanari . Si alguien tiene fuentes para encuestas, etc. sobre este tema, podría publicarlo en comentarios o editar esta respuesta (lo haré en sentido horario)
Referencias:
- Encuesta de Achlioptas
- Dónde están los problemas realmente difíciles
- Refinando la transición de fase en la búsqueda combinatoria
fuente
Por un lado, la gran mayoría de las instancias serán insatisfactorias, como se dijo en el comentario de Suresh. (De hecho, supongo que si muestra una de estas instancias de manera uniforme al azar, ya debería tener una buena probabilidad de incluir las ocho negaciones como cláusulas para algún triple variable, es decir, trivialmente insatisfactorio).2El | doEl |
Por otro lado, podemos limitar el número de instancias satisfactorias por el número que satisface la asignación de todo cero: estos serían , como para cada triplete de variables allí es una cláusula que no podemos usar.2( 7 / 8 ) | doEl |
Entonces se puede limitar el número de instancias satisfactorias multiplicando esto por . Dado que , supongo que esto solo cambia un término de orden menor ya ...| C | = O ( n 3 )2norte El | doEl | =O( n3)
fuente
Esta respuesta solo se ocupa de la tasa de crecimiento del número de instancias satisfactorias.
fuente