Melhores limites superiores no SAT

43

Em outro tópico , Joe Fitzsimons perguntou sobre "os melhores limites inferiores atuais no 3SAT".

Eu gostaria de seguir o outro caminho: qual é o melhor limite superior atual no 3SAT? Em outras palavras, qual é a complexidade de tempo do solucionador SAT mais eficiente?

Em particular, é concebível encontrar um algoritmo subexponencial (ainda super polinomial) para o SAT?

cc.complexity-theory ds.algorithms sat upper-bounds MS Dousti
fonte

2

Eu não sei sobre resultados analíticos, mas você pode encontrar resultados experimentais aqui baldur.iti.uka.de/sat-race-2010/results.html (veja os links "HTML")

Radu GRIGore

1

o título desta pergunta é um pouco enganador, devido à existência dessa pergunta: cstheory.stackexchange.com/questions/1295/sat-solver-download . Eu acho que você pode reformular como 'Melhores limites superiores no SAT'?

Suresh Venkat

@Suresh: A pergunta a que você está se referindo se refere ao "#SAT", enquanto este corresponde ao SAT. Além disso, essa pergunta foi feita cerca de uma semana após esta. De qualquer forma, você ainda sugere mudar o título desses?

MS Dousti 25/09/10

sim, porque um "SAT Solver" é um objeto bem conhecido específico - uma base de código real para resolver o SAT. O Google ficará confuso e redirecionará as pessoas que procuram código aqui :).

Suresh Venkat

4

Em relação à motivação para esta pergunta, pensei que várias pessoas haviam tentado resolver SAT nas instâncias 17x17. Parece ser a fronteira do que pode ser tratado com um solucionador SAT. Você poderia tentar um solucionador paralelo, mas eu fiquei com a impressão, com base nas postagens de Bill Gasarch, de que você precisaria de um esforço em larga escala. Você também pode aplicar um solucionador SMT com uma teoria adequada ou usar um solucionador de restrições que implemente uma restrição global que tenha um propagador eficiente. Em cada um desses casos, a nova idéia seria expressar uma propriedade importante que é difícil de fazer usando cláusulas.

András Salamon

38

Existem dois tipos de "melhores" solucionadores de SAT, um para teoria e outro para prática.

Teoria

Kazuo Iwama, Kazuhisa Seto, Tadashi Takai, Suguru Tamaki, " Algoritmos Aleatórios Aprimorados para 3-SAT ", ISAAC 2010.

randomizado para 3SAT. $O(1.32113^n)$

Timon Hertli, Robin A. Moser, Dominik Scheder, " Melhorando o PPSZ para 3-SAT usando variáveis críticas ", 2011.

randomizado para 3SAT. $O(1.321^n)$

Konstantin Kutzkov, Dominik Scheder, " Usando o CSP para melhorar o determinístico 3-SAT ", 2010.

determinístico para 3SAT. $O(1.439^n)$

Prática

Verifique a conferência SAT para obter resultados da competição para cada ano.

Tian Liu
fonte

Encontrei um link para Iwama et al. papel . Então, realmente o melhor e mais recente resultado para a solução de SAT até agora?

O ({1.32113}^{n})

$O(1.32113^n)$

MS Dousti 9/09/10

@ Sadeq: Acho que sim, mas apenas para 3-SAT, não SAT.

Tian Liu

2

Agora, o melhor algoritmo está no tempo de Timon Hertli, Robin A. Moser e Dominik Scheder.

O ({1.321}^{n})

$O(1.321^n)$

Tian Liu

10

Mais uma atualização: no FOCS 2011, Timon Hertli ( arxiv.org/abs/1103.2165 ) provou que o algoritmo PPSZ resolve todas as instâncias 3SAT em tempo.

{1.308}^{n}

$1.308^n$

Ryan Williams

21

Eu não conheço nenhum algoritmo aleatório com erro zero (ou algoritmos coNE / Eadvice ,
para esse assunto) para SAT que tenham limites melhores que os algoritmos determinísticos conhecidos,
independentemente de prometer ou não haver no máximo uma tarefa satisfatória.

O algoritmo HSSW derandomizing para 3-SAT mostra que

"O problema 3-SAT é deterministicamente solucionável no tempo ." $\overset{\sim}{O}(1.3303^n)$

A des randomização do PPSZ para o Unique-k-SAT mostra que:

"Para um 3-CNF exclusivamente satisfatório (resp. 4-CNF) em variáveis, a atribuição satisfatória pode ser encontrada em tempo de execução determinístico no máximo (resp. ) ". $n$
$O\hspace{.02 in}(1.3071^n)$ $O\hspace{.02 in}(1.4699^n)$

3-SAT mais rápido e mais simples - os limites de SAT exclusivos para o PPSZ Hold in General mostram que (originalmente mencionado no comentário de Ryan )

"Existe um algoritmo aleatório para 3-SAT com
erro unilateral que é executado no tempo ." $O\hspace{.02 in}(1.30704^n)$

"Existe um algoritmo aleatório para 4-SAT com
erro unilateral que é executado no tempo ." $O\hspace{.02 in}(1.46899^n)$

A quebra da barreira PPSZ para o 3-SAT exclusivo
reivindica um resultado que pode ser resumido da seguinte forma:

"Existe um algoritmo aleatório para o exclusivo 3-SAT, de modo que para e o número real que permite que o tempo de execução do artigo anterior vinculado ao 3-SAT seja expresso como , algoritmo roda do papel de corrente em tempo . " $\: \epsilon = 1\hspace{-0.03 in}\big/\hspace{-0.06 in}\left(\hspace{-0.03 in}10^{\hspace{.02 in}24}\hspace{-0.04 in}\right) \:$
$S$
$\: O\hspace{-0.04 in}\left(2^{(S+o(1))\cdot n}\right) \:$ $\;$ $\: O\hspace{-0.04 in}\left(2^{(S-\epsilon+o(1))\cdot n}\right)$

Comunidade
fonte

16

O algoritmo de Schoening é um algoritmo probabilístico para k-SAT com tempo de execução , em que . Isso resulta em um algoritmo para 3SAT, um algoritmo para 4SAT, etc. $O(a^n)$ $a = 2(k-1)/k$ $O(1.33334^n)$ $O(1.5^n)$

O algoritmo também foi (quase completamente) des randomizado por Moser e Scheder, que fornecem um algoritmo determinístico para resolver o tempo de execução do kSAT que é a mesma constante de antes e pode ser arbitrariamente pequeno. $O((a+\epsilon)^n)$ $a$ $\epsilon>0$

Nota: Nesta resposta, a grande notação Oh oculta fatores pol (n). Eu queria usar a notação , mas ela não está sendo renderizada corretamente. $O^*$

Robin Kothari
fonte

1

Por que você diz "quase completamente"? Perdi alguma coisa no jornal?

András Salamon

1

Existe um algoritmo determinístico para k-SAT por oito pessoas, então, por favor, perdoe-me por não mencionar todas elas. Aqui está o link: bindinghub.elsevier.com/retrieve/pii/S0304397501001748 . Portanto, para , temos e não é tão bom quanto outros limites para o 3-SAT apresentado aqui, mas para o k-SAT é o melhor, tanto quanto eu sei.

O ((2 - \frac{2}{k + 1})^{n})

$O((2 - \frac{2}{k + 1})^n)$

k = 3

$k = 3$

O ({1.5}^{n})

$O(1.5^n)$

Grigory Yaroslavtsev

4

Eu disse "quase completamente" apenas para indicar que há um fator épsilon lá. Eu acho que seria de esperar que uma des aleatorização completa atinja o mesmo tempo de execução (até fatores polinomiais). Ou talvez isso não seja razoável de se esperar.

Robin Kothari

1

@Grigory Yaroslavtsev: O algoritmo determinístico do Moser-Scheder para o kSAT que mencionei mais rapidamente que o que você citou? Estou esquecendo de algo?

Robin Kothari

1

Eu só estava preocupado com esse na sua notação, então é realmente mais rápido. Parece que o artigo apareceu no arXiv há apenas alguns dias: arxiv.org/PS_cache/arxiv/pdf/1008/1008.4067v1.pdf , então não admira que eu não soubesse disso.

ϵ

$\epsilon$

Grigory Yaroslavtsev

12

Como já foi mencionado, se você estiver interessado em garantias teóricas de tempo de execução, essa pergunta é uma duplicata.

Mas gostaria de ressaltar que, se você realmente deseja resolver um problema concreto (como o problema de cores mencionado), acho que não faz absolutamente nenhum sentido estudar os limites teóricos superiores.

Mesmo que você queira evitar aspectos de "engenharia", sugiro que você faça alguns solucionadores SAT populares, experimente-os e veja o que acontece (a maioria deles pode ler o mesmo formato de arquivo DIMACS, por isso é fácil tentar diferentes solucionadores). Você pode ter surpresas positivas e negativas. Recentemente, tive uma família de instâncias do SAT; um monte de instâncias com dezenas de milhares de variáveis e mais de um milhão de cláusulas acabou sendo fácil de resolver, enquanto instâncias aparentemente mais simples com apenas centenas de variáveis e milhares de cláusulas eram difíceis demais para qualquer solucionador que eu tentasse.

Jukka Suomela
fonte

8

Além do resumo de Jukka, também é importante notar que existem dois tipos principais de solucionadores de SAT: aqueles baseados na propagação de pesquisas, que funcionam bem para instâncias aleatórias de SAT, e aqueles que usam o aprendizado de cláusulas combinado com a resolução da unidade, que tendem a funcionar bem descobrir a estrutura combinatória. Estes têm um comportamento bem diferente. Os piores casos para solucionadores de SAT tendem a ser instâncias que não são satisfatórias, mas onde o espaço dos nogoods possui uma estrutura complexa que não permite muita poda. Infelizmente, as instâncias combinatórias tendem a ser desse tipo.

András Salamon

11

Timon Hertli, " 3-SAT mais rápido e mais simples - limites de SAT exclusivos para retenção PPSZ em geral ", FOCS 2011.

determinístico para 3SAT. $O(1.308^n)$

Kaveh
fonte

Suponho que, quando alguém apresentar um limite superior melhor, ele citará este artigo. Houve apenas uma citação neste artigo, que é "Um algoritmo de satisfação e dureza de caso médio para fórmulas sobre a base binária completa". E eles parecem falar apenas sobre certos tipos de fórmulas. Portanto, este parece ser o melhor limite superior até agora.

Tayfun Pay

@TayfunPay: O artigo de baixo na minha resposta cita esse artigo.

$\:$

$\;\;\;\;$

@RickyDemer Uhuh! é um limite melhor do que isso? A notação não é tão clara para mim.

Tayfun Pay

@TayfunPay: Sim, e você pode pesquisar os dois documentos, conforme descrito a seguir. Na página 5 do artigo geral 3-SAT, eles fornecem o valor de , relatam o tempo de execução do algoritmo PPSZ para o k-SAT exclusivo em termos de e dizem que têm o mesmo limite para o k-SAT geral. Na parte superior da página 11, esse artigo diz que seu algoritmo fornece o mesmo limite que o PPSZ, o que significa que eles não mostraram nada mais do que eu mencionei na minha frase anterior. (continuação ...)

$\:$

S_{3}

$S_3$

S_{k}

$S_k$

$\:$

$\hspace{.35 in}$

(... continua) Na página 2 do artigo 3-SAT exclusivo, eles dão o valor de e dizem que seu algoritmo fornece um limite que é melhor que por uma quantidade exponencial explícita . Como da minha frase anterior é igual a da frase anterior, o limite do papel 3-SAT exclusivo é exponencialmente melhor do que o papel 3-SAT geral.

$\:$

S

$S$

2^{S \cdot n}

$2^{S\cdot n}$

$\:$

S

$S$

S_{3}

$S_3$

$\;\;\;$

8

É impossível para o 3SAT ter algoritmos subexponenciais, a menos que a hipótese do tempo exponencial seja falsa.

Kazuo Iwama, Suguru Tamaki, Limites superiores melhorados para o 3-SAT , 2004.

algoritmo aleatório com tempo de execução esperado para 3SAT. $O({1.324}^n)$

Daniel Rolf, Limite Aprimorado para o PPSZ / Algoritmo de Schoning para 3-SAT , 2005.

$O({1.32216}^n)$

Mohammad Al-Turkistany
fonte

15

Isso não é uma tautologia?

Tsuyoshi Ito

1

2^{o (n)}

$2^{o(n)}$

O trabalho de Kazuo Iwama et al. (2004) é mais recente que a de Schoening (1999). Gostaria de saber se resultados ainda mais recentes estão disponíveis.

MS Dousti

8

Para evitar a possibilidade de confusão, meu último comentário refere-se à primeira frase da resposta: "É impossível para o 3SAT ter algoritmos subexponenciais, a menos que a hipótese do tempo exponencial (ETH) seja falsa". Meu entendimento é que o tempo exponencial hipótese é a própria hipótese que afirma que não há algoritmo para o 3SAT cujo tempo de execução é subexponencial (ou seja, 2 ^ {o (n)}) no número de variáveis.

Tsuyoshi Ito

10

E para evitar mais confusão, acrescentarei que, quando Tsuyoshi postou seu comentário, a resposta continha apenas uma frase, o que o tornou muito apropriado.

Robin Kothari

7

Este post lida com os limites superiores no SAT. Este um lida com melhores limites inferiores. Este link fornece detalhes da competição anual comparando as implementações do SAT Solver, todas disponíveis para download. Para simplificar, você pode começar com o SAT4J , uma biblioteca baseada em Java para solução de SAT.

Dave Clarke
fonte

Acontece que essa pergunta já foi feita antes; Eu simplesmente não o vi quando procurei no site. A resposta de Tian Liu na questão dos limites superiores é exatamente o que eu estava procurando. Obrigado pelos links, dave!

Daniel Apon

1

Esta é uma evidência que eu gasto muito tempo aqui ;-)

Dave Clarke

nós estamos contentes que você fazer :)

Suresh Venkat

2

Não tenho certeza se eu recomendaria o sat4J, além de ser significativamente mais lento que o estado da arte, mas também um pouco mais complexo. É verdade, no entanto, que é bem personalizável devido à estrutura orientada a objetos. O MiniSat é muito bem escrito e o 2.2 é de última geração.

Mikolas

3

O melhor algoritmo determinístico para o 3-SAT agora tem o limite superior 1.32793 ^ n, consulte https://arxiv.org/abs/1804.07901 por Sixue Liu. Basicamente, os limites superiores para todo o k-SAT foram aprimorados neste documento.

ON KI Wong
fonte

Melhores limites superiores no SAT

Respostas:

Teoria

Prática