Representando de forma compacta o conjunto de soluções de uma instância SAT

Esta questão surgiu em minha mente depois de ler as contribuições de András Salamon e Colin McQuillan para minha pergunta anterior Contando soluções de fórmulas Monotone-2CNF .

EDIT 30 ^th março 2011
questão Adicionado n ° 2.

EDIT 29 ^th outubro 2010
Pergunta reformulada após proposta András formalizá-la através da noção de representação legal de um conjunto de soluções (já modificado sua noção um pouco).

Seja uma fórmula genérica de CNF com variáveis. Seja seu conjunto de soluções. Claramente,pode ser exponencial em . Letn S | S | n R S $F$$n$$S$$|S|$$n$$R$ser uma representação de . Diz-se que é bom se, e somente se, os seguintes fatos forem verdadeiros:$S$$R$

1. $R$ tem tamanho polinomial em .$n$
2. $R$ permite enumerar as soluções em com atraso polinomial.$S$
3. | S $R$ permite determinarem tempo polinomial (ou seja, sem enumerar todas as soluções). $|S|$

Seria ótimo se fosse possível, em tempo polinomial, criar um para cada fórmula.$R$

Questões:

1. Alguém já provou que existe uma família de fórmulas para as quais uma representação tão agradável não pode existir?
2. Alguém estudou a relação entre a representação de e as simetrias exibidas por ? Intuitivamente, as simetrias devem ajudar a representar compactamente, pois evitam a representação explícita de um subconjunto de solução quando se resume a apenas uma solução (ou seja, de cada você pode recuperar todos os outros aplicando uma simetria apropriada, assim cada é ele próprio representativo de todo )F S S ' ⊂ S S « s i ∈ S ' s j ∈ S ' s i ∈ S ' S $S$$F$$S$$S' \subset S$$S'$$s_i \in S'$$s_j \in S'$$s_i \in S'$$S'$

Como afirmado (revisão 3), a pergunta tem uma resposta simples: não.

A razão é que, mesmo para a classe altamente restrita de representações dada por circuitos booleanos com portas AND, OR e NOT, não são conhecidos limites inferiores não triviais. (Claramente, um circuito que representa também representará S implicitamente, e é fácil enumerar as soluções alterando as entradas para o circuito.)$F$$S$

Para representações ainda mais restritas, como circuitos monofônicos ou de profundidade constante, os limites inferiores exponenciais são conhecidos. Também existem limites inferiores exponenciais para representar fórmulas no formato CNF ou DNF, embora possam ser vistos como casos especiais de circuitos de profundidade constante. Finalmente, as representações do BDD podem ser vistas como formas compactas de DNF, mas existem fórmulas para as quais o BDD requer tamanho exponencial para qualquer pedido de variável.

Para tornar sua pergunta mais precisa, considere a resposta de @ Joshua com mais detalhes e esclareça o que você entende por "trivial para enumerar todas as soluções".

Para a revisão 4, observe a declaração sobre o tamanho do BDD. Parte do que você parece estar se perguntando é: existe uma representação mais compacta das fórmulas DNF do que os BDDs? Permita que "o BDD tenha tamanho superpolinomial" signifique "todo BDD representando a mesma função que B , independentemente da ordem das variáveis, tenha tamanho superpolinomial" e permita que "boa representação" signifique "uma representação que permita que as soluções sejam enumeradas com atraso polinomial". Essa questão mais específica se torna:$B$$B$

existe uma família de fórmulas e uma representação legal que tenha tamanho polinomial enquanto seus BDDs tenham tamanho superpolinomial?

Isso captura a essência do que você está perguntando?

[Esta resposta foi uma resposta à versão anterior à Revisão 6 de 29 de outubro de 2010.]

$R(\varphi)$$S(\varphi)$$\varphi$$R$$|R(\varphi)| \leq poly(n)$$\varphi$$n$$A$$A(R(\varphi)) = S(\varphi)$$A$$R(\varphi))$$poly(n, |S|)$

$S$$R$$A$$|S| \leq poly(n)$$R(\varphi) = (0, S)$$|S| \geq 2^{\Omega(n)}$$R(\varphi) = (1, \varphi)$$A(0, S)$$S$$A(1, \varphi)$$S$$\varphi$$|S| = 2^{\Omega(n)}$$O(|S|)$

$R$$A$$p$$S$$poly(n)$$S$$p$$|S|$$p$$A$$|S|$

$R$$poly(n, |\varphi|)$$P \neq PromiseUP$$\varphi$$A(R(\varphi))$$\varphi$$poly(n)$