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

12

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?

Tayfun Pay
fonte
17
Não acho que exista uma única definição universalmente aceita.
Tsuyoshi Ito 30/01
5
Ainda outra escolha diferente que você pode fazer é escolher um número fixo de cláusulas (com ou sem substituição) ou escolher uma amostra de Poisson (cada cláusula é incluída independentemente com uma probabilidade fixa).
David Eppstein
4
@ Tsuyoshi, Geekster: Eu concordo com Tsuyoshi, tanto quanto sei que os SAT Solvers não precisam de nenhuma definição de Random k-SAT, qualquer que seja a técnica que eles usem (DPLL, pesquisa local, propagação de pesquisas). Estou 100% certo de que qualquer SAT Solver sério removerá cláusulas duplicadas, cláusulas tautológicas e literais duplicados antes de iniciar a pesquisa. Alguns solucionadores também removem cláusulas subsumidas.
Giorgio Camerani
4
Eu não acho que exista uma resposta para a pergunta no formulário atual, porque nenhuma definição parece "mais correta" do que outras e "contras e prós" presumivelmente dependem do que você deseja usar resultados no k-SAT aleatório. Votei para fechá-lo como uma questão não real.
Tsuyoshi Ito 30/01
4
Eu acho que a questão pode ser reapresentada, removida a parte "mais correta" e se concentrar nos prós e contras de alguns resultados específicos. (Ou a resposta pode passar por cada resultado possível.) Como essa pergunta é de alguma forma semelhante a uma pergunta sobre cortes mais esparsos que parece estar dentro do escopo sem argumentos, pessoalmente, eu gostaria de ver que a pergunta permanece aberta.
Hsien-Chih Chang #

Respostas:

15

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 ".

m2k(nk)

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/(2k(nk))N=(m2)A(n,m,k)=pN=(m2)/2k(nk)

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 )km=O(2kn)k3m=O(2kn)

A(n,m,k)=(m2)/2k(nk)=O(m2)/O(nk)=O(n2)/O(nk) .

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.k3limnO(n2)/O(nk)=0k

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
Huck Bennett
fonte
14

[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.

Kyle Jones
fonte
3
Gerando problemas difíceis de satisfação por Mitchell, Selman e Levesque. A seção 4 descreve o que eles chamam de "K-SAT aleatório". O jornal não fala em relaxar as restrições; isso vem da modificação de um gerador 3SAT aleatório e da alimentação de várias instâncias em um solucionador SAT típico baseado em DPLL.
Kyle Jones
5
"A definição mais correta é a que produz a transição de fase sat / unsat em cerca de 4,26 cláusulas por variável para o 3SAT aleatório." Você deve estar brincando.
Tsuyoshi Ito
1
@ Tsuyoshi: Embora "mais correto" seja definitivamente um trecho, acho que o argumento é que esta versão é padrão e uma das melhores estudadas.
Huck Bennett
2
Você está fazendo uma afirmação bizarra de que 4,26 é o número mágico que distingue uma definição específica do termo "k-SAT aleatório" como a mais correta. Se isso não é uma piada, não sei o que dizer.
Tsuyoshi Ito
4
Não, estou afirmando que a descoberta da transição de fase e todas as pesquisas e documentos subseqüentes concordam com a definição padrão de k-SAT aleatório, que é a definição que eu dei. Se você usar uma definição diferente, muitos papéis não farão sentido para você, porque seus resultados não corresponderão aos deles. Se você estiver trabalhando em um solucionador SAT, encontrará instâncias fáceis em que todos os artigos relacionados que li dizem que você deve encontrar trabalhos difíceis. Não há nada de mágico nisso, apenas uma convenção estabelecida neste momento. Se você quiser citar contra-exemplos, faça isso.
Kyle Jones