Número de instâncias de problemas SAT (satisfação booleana) do tamanho N?

Presumo que o tamanho de uma instância do problema SAT seja medido pelo número de variáveis ​​(booleanas). Qual é o número total de instâncias de problemas SAT de tamanho N?

Eu acho que isso equivale a contar o número de fórmulas "distintas" que podem ser formadas por N variáveis ​​booleanas, usando uma forma normal, como CNF ou DNF.

Atualização: esta pergunta é parcialmente respondida para o caso 3SAT: https://cstheory.stackexchange.com/q/2168/15553

e o número de cláusulas distintas é:

Se você considerar a Forma Normal 3-Conjuntiva (3CNF) (cada cláusula possui exatamente três literais) e permitir cláusulas com variáveis ​​repetidas, é fácil ver que usar $N$ variáveis, o número de diferentes cláusulas 3SAT é $(2N)^3$ ($2N$ porque todo literal pode parecer desnegado ou negado).

Portanto, o número total de fórmulas 3CNF distintas (sem cláusulas repetidas) é $2^{(2N)^3}$.

Mas tenha cuidado, porque o "tamanho" de uma fórmula 3CNF (por exemplo, considerado como entrada de um problema de decisão) geralmente é o tamanho de sua representação. Por exemplo, usando o alfabeto a fórmula 3CNF pode ser representado com a sequência:$\Sigma = \{0,...,9,``,",-\}$$(x_1\lor\bar{x}_2\lor x_3)\land (\lor x_2 \lor \bar{x}_3 \lor \bar{x}_4)$

1,-2,3,2,-3,-4

e seu comprimento é 14.

Uma cláusula é composta de literais sobre n variáveis. Vamos supor que uma instância seja um subconjunto de cláusulas distintas . Obviamente, podemos calcular o número de instâncias como o conjunto de cláusulas, mas isso requer que primeiro esclareçamos o que consideramos uma cláusula válida.

Em geral, cada variável será representada por um ou ambos de seus literais, ou então não será representada . Se a variável for representada, ela poderá ser representada apenas pelo literal positivo, apenas pelo literal negativo ou por ambos. Como existem 4 casos possíveis para cada variável e n variáveis, deve haver cláusulas possíveis. Excluindo a cláusula nula, temos total de cláusulas e, excluindo a instância nula, possíveis instâncias.$4^n$$4^n -1$$2^{4^n - 1}-1$

Obviamente, cláusulas que contêm os dois literais de qualquer variável não são particularmente úteis; cada um é satisfeito por cada tarefa. Como essas cláusulas realmente não adicionam restrições, vamos restringir nossa atenção às cláusulas restritivas .

Ao fazer isso, eliminamos a possibilidade de qualquer variável pegar os dois literais; portanto, temos três casos possíveis por variável ou cláusulas possíveis. Excluindo a cláusula nula e a coleção nula novamente, temos instâncias possíveis.$3^n$$2^{3^n - 1}-1$

Para k-SAT, cada cláusula possui exatamente k literais. Obviamente, existem maneiras de selecionar k variáveis. Como precisamos exatamente k literais por cláusula, no entanto, só podemos representar cada variável com seu literal positivo ou negativo. Portanto, deve haver cláusulas k e instâncias de k-sat.$n\choose k$$2^k{n \choose k}$$2^{2^k{n \choose k}}-1$

Por fim, observe que também podemos determinar quantas instâncias contêm exatamente cláusulas c.

• Para todas as cláusulas possíveis, excluindo a cláusula nula:${4^n-1}\choose c$
• Para cláusulas restritivas:${3^n-1} \choose c$
• Para cláusulas k:${{2^k}{n\choose k}\choose c}$