Fórmula mais curta para um CNF monótono de n termos

10

Uma fórmula CNF monótona com m termos em n variáveis ​​( ) é uma fórmula da forma , em que cada é um OR de algum subconjunto das variáveis e varia de a . f ( x 1 , , x n ) = C i C i x 1 , , x n i 1 mx1,,xnf(x1,,xn)=CiCix1,,xni1m

Por exemplo, é uma fórmula CNF monótona com 2 termos em 4 variáveis.(x1x3x4)(x2x4)

Estou procurando a fórmula mais curta (não necessariamente monótona, não necessariamente CNF, qualquer fórmula serve!) No mesmo conjunto de variáveis ​​que representa a mesma função que uma fórmula CNF monótona específica em n variáveis ​​com n termos. (Observe que o número de termos e variáveis ​​é o mesmo.)

Uma maneira óbvia de construir uma fórmula é expandir a definição de CNF fornecida, o que nos dará uma fórmula de tamanho . (Vamos definir o tamanho de uma fórmula como o comprimento da fórmula quando ela é escrita como uma string.) Quero saber se essa é a construção geral mais eficiente ou se, para cada CNF monotônico de n termos, existe uma fórmula do tamanho .o ( n 2 )O(n2)o(n2)

Eu só quero saber se isso é possível, não estou realmente interessado em um algoritmo. Se isso não for possível, uma função que serve como um contra-exemplo seria ótima. Ponteiros para onde eu posso encontrar uma resposta na literatura também são apreciados.

EDIT: Estou adicionando um exemplo para tornar a coisa mais clara.

Digamos que a fórmula de entrada seja . Esta é uma fórmula monótona de CNF. Uma fórmula mais curta que representa a mesma função é a seguinte: .x 1( x 2x 3f=(x1x2)(x1x3)(x1xn)x1(x2x3xn)

Robin Kothari
fonte

Respostas:

11

Você pode obter um limite inferior usando um argumento de contagem: existem CNFs termm em variáveis ​​(isso é fácil, mas requer apenas um pouco de cuidado para verifique se não há excesso de contagem), mas existem fórmulas de (ou mesmo circuitos) de tamanho no máximo . e x p ( n 2 ) n n e x p ( s log s ) sΩ(n2/logn)exp(n2) nnexp(slogs)s

Parece que vencer o último fator será difícil, pois exigiria provar um limite quadrático inferior ao tamanho da fórmula, e meu palpite é que as poucas técnicas existentes para isso não são suficientes. pode até ser a resposta certa - pelo menos para o tamanho do circuito - usando alguma técnica semelhante a quatro russos .O ( n 2 / log n )lognO(n2/logn)

Noam
fonte
Perfeito, obrigado! O fator log n não é realmente tão importante para mim, então isso responde completamente à minha pergunta.
Robin Kothari
2

Considere que, para qualquer CNF, você pode calcular o conjunto de implicados primos (dos quais qualquer mínimo deve ser um subconjunto), executando o fechamento sob resolução e aplicando a eliminação da subsunção.

No entanto, no caso de qualquer CNF monótono , o fechamento da resolução de é (como não existem literais negativos, não há resolução possível). Portanto, o CNF mínimo é o conjunto de primos implicados, que é precisamente a fórmula que você já possui.F FFFF

Claro, suponho que você não queira introduzir novas variáveis.

Se você quiser garantir que você tenha alguma fórmula que tenha termos, como você sugere, a única maneira de conseguir isso é expandir algumas das cláusulas adicionando variáveis ​​ausentes. Qualquer CNF deve ter o mesmo número de literais (a medida tamanho que você sugere que eu acredito) para um fixo e .f nnfn

MGwynne
fonte
Bom, eu gosto disso. (De passagem, no caso de um caso DNF monótono, @ Robin, acredito que isso possa ser interessante: citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.69.4716 )
Daniel Apon
11
Eu não tenho certeza se entendi. O tamanho mínimo de CNF pode ser a fórmula monótona de CNF que eu já tenho, mas estou procurando a menor fórmula de comprimento de qualquer tipo. Não precisa ser CNF ou monótono. Vou editar minha pergunta para deixar isso mais claro.
Robin Kothari
11
Ah entendo. Bem, o que eu estava dizendo cobre se for para CNF. Se puder ser uma fórmula proposicional arbitrária, preciso pensar mais.
MGwynne