Fórmula CNF equivalente más corta

18

Sea una fórmula CNF satisfactoria con n variables y m cláusulas. Sea S F 1 el espacio de solución de F 1 .F1nmSF1F1

Considere el problema de determinar, dado , otra Fórmula CNF F 2 con el mismo conjunto de variables que F 1 , con S F 2 = S F 1 (el mismo espacio de solución que F 1 ), pero con la menor cantidad posible de cláusulas ( el único objetivo es minimizar el número de cláusulas, por lo que cuántos literales puede tener cada cláusula no es relevante).F1F2F1SF2=SF1F1

Pregunta

¿Alguien ya investigó este problema? ¿Hay algún resultado en la literatura al respecto?

Como ejemplo, considere la siguiente Fórmula CNF (cada fila es una cláusula): F1

x 2x 3x 4 ¬ x 1x 2x 4 ¬ x 1x 2¬ x 3 ¬ x 1x 3x 5 ¬ x 1x 2¬ x 5x1x2x3
x2x3x4
¬x1x2x4
¬x1x2¬x3
¬x1x3x5
¬x1x2¬x5

y la siguiente fórmula : F2

x 2x 3x 4 ¬ x 1x 3x 5 ¬ x 1x 2x1x2x3
x2x3x4
¬x1x3x5
¬x1x2

ambos tienen el mismo espacio de solución, pero mientras tiene 6 cláusulas, F 2 solo tiene 4 . F16F24

Finalmente, considere la siguiente fórmula : F3

¬ x 1x 3x 5 ¬ x 1x 2x2x3
¬x1x3x5
¬x1x2

El espacio de solución es nuevamente el mismo, pero con solo cláusulas.3

Giorgio Camerani
fuente
2
@tsuyoshi Creo que quiere obtener una fórmula cnf que se compone de un número mínimo de cláusulas con el mismo espacio de solución
Tayfun Pay
1
@ TsuyoshiIto: Sí, quiero minimizar el número de cláusulas. No planteo ninguna restricción sobre el número de literales que puede tener cada cláusula.
Giorgio Camerani
1
Para cualquier definición razonable de "pequeño", el problema es NP-hard. Fórmula A CNF es satisfiable si y sólo si es no equivalente a la fórmula "False", que tiene cero cláusulas.
Jeffε
1
La Sección 6 de citeseerx.ist.psu.edu/viewdoc/… menciona que el problema de determinar si existe una fórmula CNF equivalente con, como máximo, un número determinado de literales es -completo. No estoy seguro de entender por qué su versión que minimiza el número de cláusulas es interesante, ya que esto está dentro de un factor de n del tamaño de la fórmula, donde n es el número de variables. Π2pnn
András Salamon
1
Además, otro resultado reciente es relevante: dx.doi.org/10.1016/j.dam.2011.05.013
András Salamon

Respuestas:

10

El problema de determinar si existe una fórmula CNF equivalente con un número dado de literales como máximo es -completo. La versión que minimiza el número de cláusulas está dentro de un factor de n del tamaño de la fórmula, donde n es el número de variables. Ver sección 6 de:Π2pnn

  • Christopher Umans, El problema de DNF mínimo equivalente y los implicantes más cortos , JCSS 63 (4), 597–611, 2001. doi: 10.1006 / jcss.2001.1775 ( preprint )

Un resultado reciente muestra que calcular un límite inferior particular para el tamaño de la fórmula CNF equivalente más corta (medida por el número de cláusulas, como usted especifica) es NP-completo. Este documento también afirma que su problema de minimizar el número de cláusulas también es -completo, citando el documento de Umans anterior, aunque por qué esto sigue no me resulta obvio de inmediato.Π2p

  • Ondřej Čepek, Petr Kučera y Petr Savický, funciones booleanas con un certificado simple de complejidad CNF , DAM 160 (4–5), 365–382, 2012. doi: 10.1016 / j.dam.2011.05.013
András Salamon
fuente
8

El problema de minización del circuito es intratable (ver los comentarios a continuación). También creo que puede interesarle la técnica que aplican algunos solucionadores de SAT (al menos hasta cierto punto) que se llama preprocesamiento de SAT. Por ejemplo, el conocido solucionador MiniSAT utiliza un minimizador CNF SatELite para preprocesar una instancia. Google Scholar también ofrece muchos resultados para el "preprocesamiento por satélite".

Juho
fuente
2
Π2p
1
Σ2P
6

La principal solución estándar / conocida para la minimización de CNF en EE es el algoritmo Quine-McCluskey, que tiene muchas implementaciones, algunas de dominio público. Sin embargo, entiendo que (no se menciona en el artículo actual de Wikipedia) la mayoría recurre a algoritmos heurísticos y codiciosos para encontrar soluciones especialmente para fórmulas grandes, es decir, no son necesarias. encuentre la solución óptima esp. para grandes instancias de entrada.

Quine-MCluskey es una generalización del trabajo con mapas de Karnough cuyos diagramas pueden tener éxito en casos pequeños.

y tenga en cuenta que puede haber múltiples soluciones óptimas en términos de fórmulas equivalentes con el mismo tamaño de cláusula (mínimo), esto se señalará en una buena referencia en el subj. encontrar el mínimo aparentemente se reduce a enumerar todas las implicaciones principales que pueden involucrar una explosión exponencial masiva en la memoria / "espacio" en comparación con el tamaño de la fórmula original.

vzn
fuente