Qual é a definição precisa de Random K-SAT?

Existem 4 restrições diferentes que podemos ter ao definir o Random K-SAT.
1) O número total de literais em uma determinada cláusula é exatamente K ou AT no máximo K
2) Um determinado literal pode ser usado com ou sem substituição na mesma cláusula (A ou A ou A)
3) Uma determinada variável pode ser usada com ou sem substituição na mesma cláusula (A ou ~ A ou ~ A)
4) Uma determinada cláusula pode ser usada com ou sem substituição em uma dada fórmula
Qual seria a definição mais "correta"? Quais são os contras e os prós do uso dessas diferentes definições?

$k$

$k$ $k$

Dois modelos principais:

O modelo aleatório Selman - cláusula repetida é permitido . Kyle deu essa boa referência nos comentários à sua resposta, mas assumiu incorretamente que o modelo não permitia cláusulas repetidas. A versão vinculada (ligeiramente diferente) do artigo contém uma discussão mais detalhada do modelo aleatório na Seção 3: "Este método de geração permite cláusulas duplicadas em uma fórmula ... No entanto, à medida que N obtém grandes duplicatas, elas se tornam raras, porque geralmente selecione apenas um número linear de cláusulas ".

$m$$2^k {n \choose k}$

Equivalência de locais de transição de fase :

No entanto, a transição de fase (limiar de 50% de satisfação) ocorre na mesma proporção de cláusula para variável, independentemente de qual desses modelos é escolhido, essencialmente pelo motivo de Selman et al. anotado em seu trabalho.

Deixe denotar o número esperado de pares de cláusulas idênticos em uma instância aleatória -SAT de Selman. A probabilidade de um determinado par de cláusulas ser idêntica é , enquanto o número total de pares de cláusulas é . Pela linearidade da expectativa, .$A(n,m,k)$$(n,m,k)$$p = 1/(2^k {n \choose k})$$N = {m \choose 2}$$A(n,m,k) = p \cdot N = {m \choose 2}/{2^k {n \choose k}}$

Pelo Teorema 3 em [1], o limite superior provável na localização da transição de fase SAT, usando o modelo Achlioptas, ocorre quando . Fixando e ajustando obtemosm = O ( 2 k n ) k ≥ 3 m = O ( 2 k n $k$$m = O(2^k n)$$k \geq 3$$m = O(2^k n)$

$A(n,m,k) = {m \choose 2}/{2^k {n \choose k}} = O(m^2)/O(n^k) = O(n^2)/O(n^k)$ .

Então, porque , , significando que na expectativa haverá zero cláusulas repetidas em torno de -SAT transição de fase ao gerar fórmulas SAT aleatórias usando o modelo Selman.$k \geq 3$$\displaystyle \lim_{n \rightarrow \infty} O(n^2)/O(n^k) = 0$$k$

Auto-promoção desavergonhada - discuto esses tópicos brevemente na Seção 4.1 da minha tese de mestrado .

Random QBF

Como se vê, a situação é muito mais interessante para QBF aleatório. Quais são os três primeiros trabalhos da AFAIK sobre QBF aleatório propuseram um novo modelo aleatório, criticando seu antecessor.

Veja os seguintes documentos:

• Cadoli et al. "Análise experimental do custo computacional da avaliação de fórmulas booleanas quantificadas". AI * IA 1997
• Gent + Walsh "Além do NP: a transição da fase QSAT". AAAI / IAAI 1999
• Chen + Interian "Um modelo para gerar fórmulas booleanas quantificadas aleatórias". IJCAI 2005

[Editado para maior clareza]

A definição mais amplamente utilizada na literatura de pesquisa é aquela que requer exatamente k variáveis ​​distintas por cláusula e sem cláusulas duplicadas. Se você relaxar a restrição de variáveis ​​distintas, grande parte da pesquisa existente não fará sentido para você, porque seus resultados não corresponderão aos resultados deles. A bem conhecida transição de fase sat / unsat ocorrerá em uma proporção de cláusula para variável diferente (se a transição existir) e você não encontrará as instâncias difíceis de SAT que você esperaria da literatura.