La fórmula más corta para un CNF monótono a término

10

Una fórmula monótona de CNF con m términos en n variables ( ) es una fórmula de la forma f ( x 1 , ... , x n ) = C i , donde cada C i es un OR de algún subconjunto de las variables x 1 , ... , x n e i varía de 1 a m .x1,,xnf(x1,,xn)=CiCix1,,xni1m

Por ejemplo, es una fórmula monótona de CNF con 2 términos en 4 variables.(x1x3x4)(x2x4)

Estoy buscando la fórmula más corta (no necesariamente monótona, no necesariamente CNF, ¡cualquier fórmula funcionará!) En el mismo conjunto de variables que representa la misma función que una fórmula CNF monótona dada en n variables con n términos. (Tenga en cuenta que el número de términos y variables es el mismo).

Una forma obvia de construir una fórmula es expandir la definición CNF dada, lo que nos dará una fórmula de tamaño . (Definamos el tamaño de una fórmula para que sea la longitud de la fórmula cuando se escribe como una cadena). Quiero saber si esta es la construcción general más eficiente o si para cada CNF monótono de término n existe una fórmula de tamaño o ( n 2 ) .O(n2)o(n2)

Solo quiero saber si esto es posible, no estoy realmente interesado en un algoritmo. Si esto no es posible, una función que sirva como contraejemplo sería excelente. También se agradecen los consejos sobre dónde puedo encontrar una respuesta en la literatura.

EDITAR: Estoy agregando un ejemplo para aclarar las cosas.

f=(x1x2)(x1x3)(x1xn)x1(x2x3xn)

Robin Kothari
fuente

Respuestas:

11

Ω(n2/logn)exp(n2) nnexp(slogs)s

lognO(n2/logn)

Noam
fuente
¡Perfecto gracias! El factor log n no es realmente tan importante para mí, por lo que esto responde a mi pregunta por completo.
Robin Kothari
2

Considere que para cualquier CNF puede calcular el conjunto de implicados primos (de los cuales cualquier mínimo debe ser un subconjunto) tomando el cierre bajo resolución y aplicando la eliminación de subsunción.

FFF

Por supuesto, supongo que no desea introducir nuevas variables.

nfn

MGwynne
fuente
Bien, me gusta. (De paso, en caso de que surja el caso monótono de DNF, @Robin, creo que esto podría ser interesante: citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.69.4716 )
Daniel Apon
1
No estoy seguro de entender. El tamaño mínimo de CNF podría ser la fórmula monótona de CNF que ya tengo, pero estoy buscando la fórmula de menor longitud de cualquier tipo. No tiene que ser CNF o monótono. Editaré mi pregunta para aclarar esto.
Robin Kothari
1
Ah, ya veo. Bueno, lo que estaba diciendo cubre si tiene que ser CNF. Si puede ser una fórmula proposicional arbitraria, entonces necesito pensar más.
MGwynne