¿Cuántas tautologías hay?

17

Dado , ¿cuántos DNF con variables y cláusulas son tautología? (¿o cuántos CNF son insatisfactorios?)k n m kmetro,norte,kknortemetrok

Anónimo
fuente
9
Un poco de motivación nos ayudaría a creer que esta no es solo una pregunta aleatoria.
Andrej Bauer el
1
@AndrejBauer: Estaba leyendo sobre solucionadores SAT y su desempeño.
Anónimo

Respuestas:

29

La respuesta depende de k , metro y norte . Generalmente no se conocen los recuentos exactos, pero existe un fenómeno de "umbral" que para la mayoría de las configuraciones de k , metro , norte , o casi todas las instancias de k -SAT son satisfactorias, o casi todas las instancias son insatisfactorias. Por ejemplo, cuando k=3 , se ha observado empíricamente que cuando metro<4.27norte , todos menos un o(1) fracción de 3-SAT casos son satisfiable, y cuando metro>4.27norte , todos menos una fracción no es satisfactoria. (También se conocen pruebas rigurosas de los límites).o(1)

Un punto de partida es "El orden asintótico del umbral k-SAT" .

Amin Coja-Oghlan también ha trabajado mucho en estos problemas de umbral de satisfacción.

Ryan Williams
fuente
5

Este es un comentario extendido para complementar la respuesta de Ryan, que trata con los umbrales donde el número de cláusulas se vuelve lo suficientemente grande como para que la instancia sea casi seguramente insatisfactoria. También se pueden calcular los umbrales mucho más grandes donde el número de cláusulas obliga a la insatisfacción cuando excede una función de .n

Tenga en cuenta que algunos problemas técnicos deben abordarse. Si las cláusulas repetidas se cuentan en , entonces m puede hacerse tan grande como se desee sin cambiar n . Esto destruiría la mayoría de las relaciones entre m y n . Supongamos que m es el número de cláusulas distintas. Necesitamos decidir sobre otro detalle, si las instancias están codificadas para que el orden de los literales dentro de una cláusula o el orden de las cláusulas dentro de una instancia importen. Supongamos que esto no es importante, por lo que dos instancias se consideran equivalentes si contienen las mismas cláusulas, y dos cláusulas son equivalentes si contienen los mismos literales. Con estos supuestos, ahora podemos vincular el número de cláusulas distintas que se pueden expresar conmmnmnm variables. Cada cláusula puede hacer que cada variable ocurra positiva o negativamente, o que no ocurra, y luego m 3 n .nm3n

Primero considere SAT sin restricción en . ¿Cuál es la mayor m tal que la instancia sea satisfactoria? Sin pérdida de generalidad, podemos suponer que la asignación a cero es una solución. Hay entonces 3 n - 2 n cláusulas diferentes consistentes con esta solución, cada una con al menos un literal negado. Por lo tanto, m 3 n - 2 n para cualquier instancia satisfactoria. La instancia que consta de todas las cláusulas que contienen cada una al menos un literal negado tiene esta cantidad de cláusulas y se satisface con la asignación de todo cero. Además, según el principio del casillero, cualquier instancia con al menos 3 nkm3n2nortemetro3norte-2norte cláusulas son insatisfactorias.3norte-2norte+1

Esto produce subconjuntos diferentes de tales cláusulas, cada una representando una instancia distinta que se satisface con alguna asignación. En comparación, el número total de instancias diferentes es 2 3 n .23norte-2norte23norte

Ahora modificando lo anterior para instancias en las que cada cláusula tiene como máximo literales, hay k i = 0 ( nkdistintos tales cláusulas, yΣ k i = 0 ( nyo=0 0k(norteyo)2yoyo=0 0k(norteyo)metroyo=0 0k(norteyo)(2yo-1)metro2yo=0 0k(norteyo)(2yo-1)2yo=0 0k(norteyo)2yo k

András Salamon
fuente
1
También produje el mismo resultado en 2008 ish. También hay funciones complementarias para literales y variables, de modo que si supone que no se repiten literales, variables o cláusulas, si más de x muchos o y muchos literales o variables ocurren respectivamente, la instancia dada no es satisfactoria. Tendría que cavar para encontrar esas dos funciones. +1
Tayfun Pay