Explicações teóricas para o sucesso prático dos solucionadores SAT?

Que explicações teóricas existem para o sucesso prático dos solucionadores de SAT, e alguém pode dar uma visão geral e uma explicação do "estilo da wikipedia", unindo-as?

Por analogia, a análise suavizada ( versão arXiv )) para o algoritmo simplex faz um ótimo trabalho ao explicar por que funciona tão bem na prática, apesar de levar um tempo exponencial na pior das hipóteses e ser NP-poderoso ( versão arXiv ).

Eu ouvi um pouco sobre coisas como backdoors, estrutura do gráfico de cláusulas e transições de fase, mas (1) não vejo como tudo isso se encaixa para fornecer uma imagem maior (se o fizer) e (2) Não sei se isso realmente explica por que os solucionadores SAT funcionam tão bem, por exemplo, em instâncias industriais. Além disso, quando se trata de estrutura do gráfico de cláusulas: por que os solucionadores de corrente são capazes de tirar proveito de certas estruturas do gráfico de cláusulas?

Só acho os resultados das transições de fase parcialmente satisfatórios nesse aspecto, pelo menos no meu entendimento atualmente limitado. A literatura de transição de fase é sobre instâncias de k-SAT aleatório , mas isso realmente explica alguma coisa sobre instâncias do mundo real? Não espero que as instâncias do SAT do mundo real se pareçam com instâncias aleatórias; Eu devo? Existe uma razão para pensar que as transições de fase nos dizem algo, mesmo intuitivamente, sobre instâncias do mundo real, mesmo que não pareçam com instâncias aleatórias?

Perguntas relacionadas que ajudam, mas não respondem completamente à minha pergunta, particularmente o pedido de amarrar as coisas em uma imagem coerente:

• Por que existe uma enorme diferença entre os solucionadores SAT?

• Quais problemas de SAT são fáceis?

• Qual é a correlação entre a largura da árvore e a dureza da instância do 3SAT aleatório?

Estou assumindo que você está se referindo solucionadores CDCL sentou-se em conjuntos de dados de referência, como os usados na competição SAT . Esses programas são baseados em muitas heurísticas e muita otimização. Houve algumas apresentações muito boas de como elas funcionam no workshop Fundamentos Teóricos da Resolução Aplicada SAT em Banff em 2014 ( vídeos ).

Esses algoritmos são baseados no algoritmo de retorno de DPLL, que tenta encontrar uma atribuição satisfatória, definindo valores para variáveis ​​e retornos quando encontra um conflito. As pessoas analisaram o impacto dessas heurísticas. Por exemplo, veja

• Hadi Katebi, Karem A. Sakallah e João P. Marques-Silva, " Estudo empírico da anatomia dos solventes modernos ", 2011

Parece que a eficiência desses solucionadores SAT nos benchmarks deriva principalmente de duas heurísticas (e suas variantes):

1. Aba heurística do VSIDS selecionando em qual variável ramificar a seguir.
2. CDCL: cláusula orientada a conflitos que aprende heurística que aprende uma nova cláusula de um conflito.

É sabido que as provas DPLL correspondem às provas em resolução. Sem o CDCL, as únicas provas de resolução que podemos obter são as de resolução em árvore que são muito mais fracas que as de resolução geral.

Existem resultados que mostram com o CDCL que podemos obter qualquer prova geral de resolução. No entanto, existem advertências, elas precisam de muitas reinicializações artificiais, ramificações artificiais e / ou pré-processamento específico, portanto não está claro quão próximas elas estão do que esses programas fazem na prática. Veja, por exemplo, o seguinte documento para obter mais detalhes:

• Paul Beame e Ashish Sabharwal, " Solvers SAT sem reinicialização com pré-processamento simples podem simular com eficiência a resolução ", 2014

O CDCL está basicamente cortando ramificações do espaço de pesquisa. Existem várias maneiras de derivar uma nova cláusula aprendida de um conflito. Idealmente, adicionaríamos um conjunto de cláusulas mínimas que implicavam o conflito, mas, na prática, elas podem ser grandes e caras de calcular. Os principais solucionadores de SAT frequentemente excluem cláusulas aprendidas regularmente e isso ajuda na prática.

O outro VSIDS heurístico mantém essencialmente uma pontuação para cada variável. Toda vez que há um conflito, todas as pontuações são ajustadas multiplicando-as com um valor <1 e adicionando uma constante às que estavam "envolvidas" no conflito. Para ver o que isso significa, pense na sequência que é 1 se a variável v estava "envolvida" no ésimo conflito. Seja uma constante fixa. A pontuação da variável no tempo é então: F ( v , i ) i 0 < α < 1 v n ∑ i < n F ( v , i ) α ( n - i $\alpha$$F(v,i)$$i$$0<\alpha<1$$v$$n$

Intuitivamente, pode-se dizer que isso tenta enfatizar variáveis ​​que foram consistentemente envolvidas em conflitos recentes. Você também pode pensar nisso como uma maneira simplista, mas extremamente barata, de prever quais variáveis ​​estarão envolvidas no próximo conflito. Portanto, o VSIDS se ramifica primeiro nessas variáveis. Pode-se afirmar que o algoritmo é essencialmente um algoritmo à prova de falhas, encontrar conflitos rapidamente. Rápido está relacionado ao menor número de conjunto de variáveis, o que significa bloquear grandes subárvores da árvore de pesquisa. Mas isso é principalmente intuição, apesar de ninguém formalizar com muito cuidado testá-lo em conjuntos de dados SAT. Executar um solucionador SAT em um desses conjuntos de dados não é barato, muito menos compará-lo com as decisões ideais (menor extensão da atribuição atual a variáveis ​​que violariam uma das cláusulas). O VSIDS também depende de quais variáveis ​​esbarramos a cada conflito; existem várias maneiras de definir quando uma variável está envolvida em um conflito.

Há resultados que mostram que a implementação específica dessas idéias corresponde a uma centralidade ponderada no tempo de vértices em gráficos dinâmicos.

Também existem sugestões de que, excluindo instâncias adversárias, como aquelas baseadas em problemas difíceis de NP, primitivas criptográficas e instâncias aleatórias (nas quais os solucionadores CDCL SAT não são bons), as demais instâncias vêm de coisas muito bem estruturadas, como verificação de software e hardware e, de alguma forma, essas as estruturas são exploradas pelos solucionadores de CDCL SAT (muitas idéias foram mencionadas como backdoors, variáveis ​​congeladas etc.), mas, na maioria das vezes, são idéias e não apresentam fortes evidências teóricas ou experimentais para apoiá-las. Eu acho que seria preciso primeiro definir rigorosamente corretamente e mostrar que as instâncias nas quais esses algoritmos funcionam bem têm a propriedade e, em seguida, mostrar que esses algoritmos exploram essas propriedades.

Algumas pessoas continuam insistindo que a proporção e os limites da cláusula são o único jogo na cidade. Isso é definitivamente falso, como qualquer pessoa que esteja um pouco familiarizada com o funcionamento dos solucionadores industriais de SAT ou que tenha algum conhecimento sobre a complexidade das provas. Há muitas coisas que fazem um solucionador SAT funcionar bem ou não em uma instância na prática e a proporção da cláusula é apenas uma das coisas que podem estar envolvidas. Acho que a pesquisa a seguir é um bom ponto de partida para aprender sobre as conexões entre a complexidade da prova e os solucionadores e perspectivas do SAT:

• Jakob Nordstrom, " Sobre a interação entre a complexidade da prova e a solução de SAT ", 2015

Curiosamente, mesmo o fenômeno do limiar é mais complicado do que a maioria das pessoas pensa, Moshe Vardi afirmou em sua palestra " Transições de fase e complexidade computacional " que o tempo médio de execução do GRASP permanece exponencial para as fórmulas aleatórias do 3SAT após o limiar, mas que o expoente diminui (depois, não está claro a rapidez com que diminui).

Por que estamos estudando solucionadores de SAT (como teóricos da complexidade)? Penso que a resposta é a mesma que para outros algoritmos: 1. compare-os, 2. encontre suas limitações, 3. projete melhores, 4. responda a questões fundamentais da teoria da complexidade.

Ao modelar uma heurística, geralmente substituímos a heurística pelo não determinismo. A questão então se torna: é um substituto "justo"? E aqui, de maneira justa, quero dizer o quão perto está o modelo para nos ajudar a responder à pergunta acima.

Quando modelamos um solucionador SAT como um sistema de prova, estamos mostrando parcialmente sua limitação, porque o algoritmo será ineficiente para declarações com limites mais baixos no sistema de prova. Mas ainda existe uma lacuna entre o que o algoritmo realmente encontra e a prova ideal no sistema de provas. Portanto, precisamos mostrar que o inverso também, ou seja, o algoritmo pode encontrar provas tão boas quanto as do sistema de provas. Não estamos perto de responder a essa pergunta, mas a quantidade de heurística que é substituída pelo não-determinismo define o quão próximo o modelo está do sistema de prova. Não espero que descartemos completamente a substituição de heurísticas por não-determinismo, caso contrário obteríamos resultados de automatizabilidade que têm consequências em problemas abertos em criptografia, etc.

Portanto, a pergunta ao olhar para um modelo se torna: quanto os modelos ajudam a explicar por que o SAT solver A é melhor que o SAT solver B? Quão úteis eles são no desenvolvimento de melhores solucionadores de SAT? O solucionador SAT encontra na prática provas que estão próximas das ótimas no modelo? ... Também precisamos modelar as instâncias práticas.

Em relação à intuição que o CDCL SAT resolve "explora a estrutura das instâncias práticas" (seja lá qual for essa estrutura), é geralmente aceita a intuição, eu acho. A verdadeira questão é dar uma explicação convincente do que isso significa e demonstrar que é realmente verdade.

Veja também a resposta de Jakob Nordstrom para desenvolvimentos mais recentes.

Estou digitando isso rapidamente devido a severas restrições de tempo (e nem sequer consegui responder mais cedo pelo mesmo motivo), mas achei que tentaria pelo menos entrar em contato com meus dois centavos.

Eu acho que essa é uma pergunta realmente ótima e passamos um tempo não trivial nos últimos anos analisando isso. (Divulgação completa: recebi grande parte do meu financiamento atual precisamente para tentar encontrar respostas para perguntas desse tipo e, em seguida, potencialmente converter idéias mais profundas no SAT em solucionadores mais eficientes de SAT.)

Se alguém tivesse que dar uma resposta de uma frase, então eu acho

ninguém realmente sabe e esta é uma área ativa de pesquisa

é tão bom quanto ele ganha. Exceto que há muito mais espaço para mais atividades, especialmente do lado da teoria.

Algumas explicações propostas (não mutuamente exclusivas), que já foram discutidas em outras respostas e comentários, são

• a) portas traseiras;
• (b) considerações de complexidade parametrizadas,
• (c) estrutura gráfica do problema da CNF,
• (d) considerações de complexidade de prova, e
• (e) transições de fase.

A partir do final (e), parece haver alguma confusão em relação às transições de fase. A resposta curta aqui é que não há razão alguma para acreditar que a razão de cláusulas para variáveis ​​seja relevante para problemas aplicados ou problemas combinatórios teóricos (também conhecidos como instâncias criadas). Mas, por alguma razão, é um equívoco não muito incomum na parte aplicada da comunidade SAT que a proporção de cláusulas para variáveis ​​deve, de alguma forma, ser uma medida geralmente relevante. A razão de cláusula para variável é muito relevante para o k-SAT aleatório, mas não para outros modelos.

Meu sentimento é que os backdoors (a) têm sido uma explicação popular, mas eu pessoalmente não tenho visto evidências convincentes de que isso explique o que acontece na prática.

A complexidade parametrizada (b) fornece uma bela teoria sobre alguns aspectos do SAT, e uma hipótese muito atraente é que as instâncias do SAT são fáceis porque tendem a estar "próximas a alguma ilha de tratabilidade". Eu acho que essa hipótese abre muitas direções interessantes de pesquisa. Como observado em algumas das respostas, existem muitas conexões entre (a) e (b). No entanto, até agora, não vejo nenhuma evidência de que a complexidade parametrizada se correlacione demais com o que está acontecendo na prática. Em particular, parece que instâncias tratáveis ​​podem ser muito, muito difíceis na prática, e instâncias sem pequenas portas traseiras ainda podem ser muito fáceis.

A explicação que me parece mais crível para instâncias industriais é (c), a saber, que a estrutura (gráfica) das fórmulas da CNF em questão deve ser correlacionada com o desempenho prático do SAT. A idéia aqui é que variáveis ​​e cláusulas de instâncias industriais podem ser agrupadas em comunidades bem conectadas com poucas conexões entre elas, e que os solucionadores de SAT de alguma forma exploram essa estrutura. Infelizmente, parece bastante difícil definir isso de maneira mais rigorosa, e igualmente infelizmente essa área sofre com uma quantidade razoável de exageros. As explicações propostas que vi até agora em artigos são bastante insatisfatórias e os modelos parecem fáceis de abater. O problema parece ser que, se alguém realmente quiser fazer isso completamente, então a matemática fica muito difícil (porque é um problema difícil) e também fica extremamente confusa (porque você precisa que seu modelo esteja próximo o suficiente da realidade para obter resultados relevantes). Em particular, os trabalhos que eu vi explicando que o desempenho da heurística VSIDS (soma de decaimento independente do estado variável) para escolhas variáveis ​​funciona bem porque explora comunidades no gráfico, a representação das instâncias é bastante pouco convincente, embora a hipótese, como tal, ainda seja muito atrativo.

Uma linha de pesquisa que eu pessoalmente busquei é se o desempenho prático do SAT se correlaciona de alguma forma com as medidas de complexidade de prova das fórmulas da CNF em questão. Infelizmente, a resposta curta parece ser que realmente não há uma conexão clara e convincente. Ainda pode haver correlações não triviais (isso é algo que estamos investigando atualmente de maneiras diferentes), mas parece que a teoria é muito agradável, limpa e bonita, e a realidade é muito confusa para que haja uma combinação realmente boa. (Em relação ao artigo Relacionando Medidas de Complexidade de Prova e Dureza Prática do SATpor Järvisalo, Matsliah, Nordström e Živný no CP '12, verificou-se que experimentos mais detalhados fornecem uma imagem muito mais complexa com conclusões menos claras --- esperamos chegar a uma versão completa do periódico relatando isso a qualquer década, mas é complicado, embora ainda seja interessante.)

Outra linha de trabalho relacionada à complexidade da prova é modelar os solucionadores SAT de ponta como sistemas de prova e provar teoremas nesses modelos para deduzir propriedades dos solucionadores correspondentes. No entanto, esse é um campo minado, pois pequenas e aparentemente inócuas opções de design no lado do modelo teórico podem levar os resultados a serem praticamente completamente irrelevantes do ponto de vista prático. Por outro lado, se alguém deseja um modelo teórico próximo da realidade para obter resultados relevantes, esse modelo fica extremamente confuso. (Isso ocorre porque o desempenho do SAT solver depende da história global de tudo o que aconteceu até agora de maneiras não triviais, e isso significa que o modelo não pode ser modular da maneira como geralmente configuramos nossos sistemas de prova - se uma etapa de derivação específica é "corrigir"

Porém, dois artigos que realmente devem ser mencionados como exceções são [Pipatsrisawat e Darwiche 2011] e [Atserias, Fichte e Thurley 2011], onde é mostrado que a cláusula orientada a conflitos que aprende os solucionadores de SAT modelados de maneira natural tem o potencial para simular polinomialmente a resolução geral e completa. Há uma lista bastante longa de artigos anteriores a [PD11] e [AFT11] que alegam essencialmente o mesmo resultado, mas todos eles têm sérios problemas com a modelagem. (É verdade que [PD11] e [AFT11] também precisam de algumas suposições para funcionar, mas elas são praticamente as mínimas que você esperaria, a menos que você esteja pedindo papéis que também mostrem que a hierarquia de complexidade parametrizada entra em colapso.)

Mais uma vez, estou escrevendo tudo isso muito rapidamente, mas, se houver um interesse substancial por qualquer uma das opções acima, eu poderia tentar elaborar (embora possa demorar um pouco para retornar a isso novamente --- sinta-se à vontade para me enviar um ping, se houver é qualquer coisa que você queira que eu comente). Como uma maneira rápida de fornecer referências, deixe-me fazer algumas auto-descaradas vergonhosas (embora a vergonha diminua um pouco quando vejo que alguns comentários também citaram algumas dessas referências):

Palestra em estilo de tutorial Sobre a interação entre complexidade de prova e resolução de SAT, apresentada na Escola Internacional de Verão sobre Satisfação, Teorias de Módulos de Satisfação e Raciocínio Automatizado em 2016, com muitas referências completas no final dos slides: http://www.csc .kth.se / ~ jakobn / research / TalkInterplaySummerSchool2016.pdf

Pesquisa de opinião um pouco mais recente e mais breve Noções básicas sobre a solução de SAT orientada por conflitos através da lente da complexidade da prova do início de 2017 (também com referências completas no final): http://www.csc.kth.se/~jakobn/research /TalkProofComplexityLensCDCL1702.pdf

Pesquisa de conexões entre a complexidade da prova e a solução do SAT: http://www.csc.kth.se/~jakobn/research/InterplayProofCplxSAT.pdf [Referência bibliográfica: Jakob Nordström. Sobre a interação entre a complexidade da prova e a resolução de SAT. Notícias do ACM SIGLOG, volume 2, número 3, páginas 19-44, julho de 2015. (Versão levemente editada, com alguns erros corrigidos.)]

Artigo SAT '16 com CDCL modelado fielmente como um sistema de prova: http://www.csc.kth.se/~jakobn/research/Trade-offsTimeMemoryModelCDCL_SAT.pdf [Referência bibliográfica: Jan Elffers, Jan Johannsen, Massimo Lauria, Thomas Magnard , Jakob Nordström e Marc Vinyals. Compensações entre tempo e memória em um modelo mais rígido de solventes CDCL SAT. Em Anais da 19ª Conferência Internacional sobre Teoria e Aplicações de Testes de Satisfação (SAT '16), Notas de Aula em Ciência da Computação, volume 9710, páginas 160-176, julho de 2016.]

Deixe-me acrescentar meus dois centavos de entendimento a isso, mesmo que eu nunca tenha realmente trabalhado na área.

Você está fazendo uma das duas perguntas: "quais são as abordagens conhecidas para provar a eficiência teórica de algum solucionador SAT para algum tipo de instância" e "por que os solucionadores SAT são eficientes na realidade".

Para a pergunta anterior, vou direcioná-lo à pesquisa de Stefan Szeider. Ele me parece ser a área atualmente mais ativa no tópico de backdoors e parametrizações FPT do SAT (que inclui ambas as abordagens estruturais, como medidas do tipo largura de árvore e os chamados conjuntos de backdoor, bem como uma mistura dos dois).

Para a última pergunta, para ser honesto, essa pergunta exata foi debatida em todos os workshops de resolução do SAT em que participei (incluindo os últimos anos), por isso não é um assunto resolvido. Mas minha impressão é a seguinte.

Primeiro de tudo, você precisa quantificar ou restringir o que você quer dizer com "na realidade". Não é verdade que os solucionadores SAT são universalmente bons para qualquer problema em que você os lance (é claro), e entre problemas diferentes, você acaba precisando de estratégias diferentes. Por exemplo, há vários sucessos recentes em que conjecturas matemáticas foram verificadas ou reforçadas por uma enorme pesquisa de computador auxiliada por um solucionador de SAT. Nesse caso, aparentemente, na maioria das vezes, as melhorias e heurísticas inteligentes ao estilo CDCL que os solucionadores modernos de SAT normalmente empregam não compram muita energia, e o jogo se resume a uma maneira inteligente de dividir seu problema de origem em partes, seguidas por (essencialmente) um algoritmo de ramificação de força bruta com um pequeno fator constante no tempo de execução.

Talvez eu esteja supervalorizando um pouco esse ponto, mas meu argumento foi que, quando os solucionadores de SAT atacaram, por exemplo, a Conjectura de Discrepância de Erdos, eles tiveram sucesso por um motivo diferente do que quando resolvem instâncias industriais derivadas de testes de circuito.

Então, perguntamos: por que os solucionadores baseados em CDCL funcionam tão bem em instâncias industriais de, por exemplo, verificação de circuitos (teste de equivalência de circuitos)? Eu achoque a visão mais poderosa (ou a visão de consenso) aqui é a estratégia de pesquisa de um CDCL para resolver géis muito bem com a estrutura dessas instâncias. Isso significa, por exemplo, que os circuitos consistem em partes relativamente complexas (denominadas clusters), interconectadas por conexões relativamente menos e mais simples, possivelmente de maneira hierárquica; e que os solucionadores de CDCL, com todas as suas heurísticas, são muito bons em (de fato) explorar isso e "projetar" esses clusters nas variáveis ​​compartilhadas, da maneira ou ordem mais útil para verificar o circuito em questão. Mas também parece ainda ser a opinião de consenso de que essa é uma explicação insuficiente (por exemplo, provavelmente não podemos explicar teoricamente a eficiência dos solucionadores de CDCL SAT nesse domínio apenas com referência à estrutura gráfica da instância).

Então, as parametrizações tratáveis ​​ajudam a explicar a última? Para ser sincero, não sei. Eu acho que provavelmente existe um efeito poderoso em jogo: as instâncias do mundo real não são o pior caso, nem são (provavelmente) realmente o caso médio, de acordo com qualquer distribuição de instância que possamos lidar. Mas provavelmente ainda vale a pena perguntar.

Existe um artigo " Relacionando Medidas de Complexidade de Prova e Dureza Prática do SAT ", de Matti Järvisalo, Arie Matsliah, Jakob Nordström e Stanislav Živný no CP '12, que tenta vincular a dureza ou facilidade de resolver certas fórmulas dos solucionadores de CDCL à prova de resolução medidas de complexidade, em particular espaço à prova de resolução. Os resultados são um tanto confusos, mas acho que é um passo na direção certa.

Não sou especialista nesta área, mas acho que o material de transição aleatória SAT / fase é mais ou menos completamente não relacionado ao material de aplicações industriais / práticas.

Por exemplo, os solucionadores muito bons para instâncias aleatórias (como https://www.gableske.net/dimetheus ) são baseados nos métodos de física estatística (propagação de crenças, etc.) acredito, enquanto os solucionadores 'gerais' muito bons (como como http://fmv.jku.at/lingeling/ ) estão usando técnicas não relacionadas (mais parecidas com o que Kaveh estava falando) eu acredito.

Mas, como eu disse, talvez não aceite minha palavra; isso é proveniente de um não especialista definido.