Por que o 2SAT está em P?

55

Eu me deparei com o algoritmo polinomial que resolve 2SAT. Eu achei desconcertante que o 2SAT esteja em P, onde todas (ou muitas outras) das instâncias do SAT são NP-Complete. O que torna esse problema diferente? O que o torna tão fácil (NL-Complete - ainda mais fácil que P)?

Cara
fonte
18
Por que as pessoas pensam que essa é uma pergunta tão ruim?
Peter Shor
12
Um aspecto interessante é que, se você deseja conhecer o número máximo de cláusulas simultaneamente satisfatórias em uma expressão 2SAT (ou seja, Max2SAT), está de volta ao NP-complete novamente.
perfil completo de Shaun Harker
11
Essa é uma pergunta horrível, porque não tem uma resposta útil, ou uma pergunta fantástica, porque a única resposta correta é "ninguém sabe".
Jeffε
12
Por favor, leia o artigo "A complexidade dos problemas de satisfação: refinando o teorema de Schaefer".
Diego de Estrada
3
Caro cara, o fato de o 2SAT estar em P é abordado em quase todos os livros de complexidade padrão, então quando você diz que acabou de notar esse fato, a pergunta parece como se você nem tivesse lido um livro de complexidade padrão.
Kaveh

Respostas:

88

Aqui está uma explicação mais intuitiva e despretensiosa ao longo das linhas da resposta de MGwynne.

Com -SAT, você só pode expressar implicações de forma , onde e são literais. Mais precisamente, a cada -clause pode ser entendido como um par de implicações: e . Se você definir como true, deverá ser verdadeiro. Se você definir como falso, deverá ser falso. Tais implicações são diretas: não há escolha, você tem apenas2abab2l1l2¬l1l2¬l2l1abba1possibilidade, não há espaço para a multiplicação de maiúsculas e minúsculas. Você pode apenas seguir cada possível cadeia de implicação, e veja se você nunca derivar tanto de e de : se você fizer isso por algum , então a fórmula 2-SAT é insatisfatível, caso contrário é satisfeita. É o caso de o número de possíveis cadeias de implicação estar polinomialmente limitado no tamanho da fórmula de entrada.¬lll¬ll

Com -SAT, você pode expressar implicações de forma , onde , e são literais. Agora você está com problemas: se você definir como verdadeiro, então ou deve ser verdadeiro, mas qual? Você tem que fazer uma escolha: você tem 2 possibilidades. Aqui é onde a multiplicação de casos se torna possível e onde a explosão combinatória surge.3abcabcabc

Em outras palavras, o -SAT é capaz de expressar a presença de mais de uma possibilidade, enquanto o -SAT não possui essa capacidade. É precisamente essa presença de mais de uma possibilidade ( possibilidades no caso de SAT, possibilidades no caso de SAT) que causa a explosão combinatória típica de problemas de NP-completos.3223k1k

Giorgio Camerani
fonte
6
Eu gostaria de poder votar mais! Uma resposta muito melhor!
MGwynne
5
@Gwynne: Obrigado pelo seu comentário muito gentil. De nada, e sua resposta é realmente muito boa!
Giorgio Camerani
8
Esta é uma boa resposta para uma boa pergunta (IMHO). Como Mac Lane escreveu: "Manipulações formais eficazes ou complicadas são introduzidas por matemáticos que, sem dúvida, têm uma idéia norteadora - mas é mais fácil declarar as manipulações do que formular a idéia em palavras. ... Uma exposição perspicaz de uma peça da matemática permite que as idéias brilhem através da exibição de manipulações ". Essa pergunta e resposta em particular ajudou "as idéias a brilharem" (para mim). Obrigado! :)
John sidles
4
@ John: De nada! ;-) Muito obrigado pelo seu ótimo e generoso comentário, eu realmente gostei. Eu não poderia concordar mais com as palavras de Mac Lane.
Giorgio Camerani
De acordo com a resposta de Giorgio Camerani, não vale a pena reduzir qualquer problema de NP para o 3SAT se você introduzir mais variáveis ​​booleanas fictícias, tiver mais cláusulas e não tiver ganho nem lucro, mas é mais preferido reduzi-lo à CNF SAT ou à satisfação booleana ou Em vez disso, circuito SAT, porque nesses problemas você tem variáveis ​​booleanas menores e cláusulas menores e isso significa que algoritmos ingênuos de força bruta, mapas de karnaugh e algoritmo Quine-McClusky têm melhor complexidade: D.
Troca de pilha de despedida
31

Considere a resolução em uma fórmula 2-SAT. Qualquer resolvente tem tamanho máximo de 2 (observe que se para cláusulas de comprimento e resp). O número de cláusulas de tamanho 2 é quadrático no número de variáveis. Portanto, o algoritmo de resolução está em P.n , m 2 n mn+m22n,m2nm

Quando você chega ao 3-SAT, pode obter resoluções cada vez maiores, para que tudo fique em forma de pêra :).

Tente traduzir um problema para 2-SAT. Como você não pode ter cláusulas de tamanho 3, não pode (em geral) codificar implicações envolvendo três variáveis ​​ou mais, por exemplo, que uma variável é o resultado de uma operação binária em duas outras. Esta é uma enorme restrição.

MGwynne
fonte
3
"Você não pode coisas codificar como implicação" - IMP-SAT também está em P (e eu acho NL)
Max
8
¬ p qpq é apenas . ¬pq
Kaveh
11
Kaveh, bom ponto, corrigido agora.
precisa saber é o seguinte
Como eu já disse quando você reduziu seu problema arbitrário de NP a Satisfação Booleana ou Circuit SAT ou CNF SAT, não reduza o problema para 3SAT, porque o problema se torna ainda mais difícil e complexo com mais variáveis ​​e cláusulas booleanas. Mesmo o algoritmo de resolução se torna menos eficiente no novo problema!
Troca de despedida Stack
20

Como Walter diz, as cláusulas do 2-SAT têm uma forma especial. Isso pode ser explorado para encontrar soluções rapidamente.

Na verdade, existem várias classes de instâncias SAT que podem ser decididas em tempo polinomial, e o 2-SAT é apenas uma dessas classes tratáveis . Existem três tipos amplos de razões para a rastreabilidade:

  1. (Rastreabilidade estrutural) Qualquer classe de instâncias SAT em que as variáveis ​​interagem de maneira semelhante a uma árvore pode ser resolvida em tempo polinomial. O grau do polinômio depende da largura máxima de instâncias na classe, onde a largura mede a distância que uma instância está de ser uma árvore. Mais precisamente, Marx mostrou que, se as instâncias têm largura submodular limitada, a classe pode ser decidida em tempo polinomial usando uma abordagem de dividir e conquistar.

  2. (Rastreabilidade do idioma) Qualquer classe de instâncias SAT em que o padrão de variáveis ​​verdadeiro-falso é "bom" pode ser resolvido em tempo polinomial. Mais precisamente, o padrão de literais define uma linguagem de relações, e Schaefer classificou as seis linguagens que levam à tratabilidade, cada uma com seu próprio algoritmo. 2-SAT forma uma das seis classes Schaefer.

  3. (Rastreabilidade híbrida) Existem também algumas classes de instâncias que não se enquadram nas outras duas categorias, mas que podem ser resolvidas em tempo polinomial por outros motivos.

    • Dániel Marx, Propriedades de hipertexto tratáveis ​​para satisfação de restrições e consultas conjunturais , STOC 2010. ( doi , preprint )
    • Thomas J. Schaefer, A complexidade dos problemas de satisfação , STOC 1978. ( doi )
András Salamon
fonte
2
Também existem argumentos baseados na estrutura do espaço da solução da literatura aleatória k-SAT que podem ser usados ​​para explicar a diferença.
Kaveh
3
@ Kaveh: minha descrição da tratabilidade híbrida deveria ser vaga o suficiente para abranger essas coisas. Por exemplo, para tipos muito especiais de instâncias, é possível argumentar a favor da satisfação com base no lema local de Lovász. Veja a pesquisa de 1997 de Pearson e Jeavons: cs.ox.ac.uk/publications/publication1610-abstract.html
András Salamon
3
Observe também que SAT é o caso especial do problema de satisfação de restrições em que cada variável pode assumir 2 valores. Quando as variáveis ​​podem assumir 3 valores, existem 10 classes de idiomas tratáveis, classificadas por Andrei Bulatov: cs.sfu.ca/~abulatov/papers/3-el-journal.ps As classes híbridas também são mais interessantes para domínios maiores.
András Salamon
10

Se você entende o algoritmo do 2SAT, já sabe por que ele está em P - é exatamente isso que o algoritmo demonstra. Eu acho que esse quadrinho ilustra meu argumento. Como você já sabe por que o 2SAT está em P, o que você provavelmente quer saber é por que o 2SAT não é difícil para o NP.

Para entender por que o 2SAT não é difícil para o NP, você deve considerar como é fácil reduzir outros problemas no NP. Para obter uma compreensão intuitiva disso, veja como o SAT pode ser reduzido para 3SAT e tente aplicar as mesmas técnicas para reduzir o SAT para 2SAT. O 2SAT não é tão expressivo quanto o 3SAT e outras variantes do SAT.

Dave
fonte