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

43

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:

Joshua Grochow
fonte
5
Esta não é uma resposta, mas não creio que muita gente ainda acredite que estruturas / backdoors de gráficos possam explicar o desempenho dos solucionadores SAT. Eles parecem mais relevantes para problemas mais difíceis, como #SAT, QBF ou compilação de conhecimento, onde você realmente precisa encontrar fatorações inteligentes, pois precisa explorar de alguma forma toda a estrutura. Para sua pergunta, estou tentado a responder "ninguém realmente sabe e essa é uma área ativa de pesquisa". Mas preciso reunir referências para mostrar o que as pessoas estão tentando e pode haver alguém com uma visão mais ampla do que eu que possa dar uma resposta melhor.
holf 30/03
2
@ Josué: O método simplex é até poderoso para o PSPACE (Fearnley e Savani, STOC 15).
Rahul Savani 30/03
1
Eu concordo com @holf. Aqui estão alguns centavos: os solucionadores de SAT recuperam mais rápido que os de CSP, porque todas as suas variáveis ​​têm um tamanho de domínio de dois. Isso não quer dizer que nenhum solucionador de CSP possa superar um solucionador SAT, mas pode ter uma variável dinâmica muito sofisticada (além de valor) ordenando heurísticas, juntamente com uma boa codificação do problema. Além disso, quando você transforma uma "instância da vida real" em uma instância de SAT, raramente termina no ponto de transição de fase devido à introdução de tantas variáveis ​​auxiliares. usually
Tayfun Pay
3
@TayfunPay: Eu não estava questionando sua experiência - de fato, 100% acredito que os problemas da "vida real" se traduzem em instâncias SAT que não estão próximas da transição de fase. Mas não acho que isso explique a facilidade de tais instâncias, como essas instâncias não são aleatórias , portanto a transição de fase (em teoria) deve ter pouco a dizer sobre elas (dureza ou facilidade).
Joshua Grochow 31/03
2
Isso já foi mencionado em outro lugar, mas é importante observar que a densidade da variável de cláusula e as transições de fase são relevantes apenas para o k-SAT aleatório e não têm nada a ver com a dureza das instâncias provenientes de problemas industriais ou combinatórios. Assim, a maior parte da discussão acima é irrelevante. Além disso, vale ressaltar que, em relação ao k-SAT aleatório, não existe um padrão real fácil-difícil-fácil --- para os sistemas de prova em que temos limites inferiores para fórmulas k-CNF geradas aleatoriamente, as fórmulas permanecem exponencialmente difíceis para constante arbitrariamente grande densidades acima do limiar.
Jakob Nordstrom

Respostas:

21

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

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:


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 )αF(v,i)i0<α<1vn

i<nF(v,i)α(ni)

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:

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.

Kaveh
fonte
1
Isso vale para instâncias SAT derivadas de fatoração de número inteiro?
Mohammad Al-Turkistany 31/03
1
Sim, mas ainda é uma . Pode muito bem piorar em alguns casos que podem ser facilmente resolvidos por uma heurística diferente usando o mesmo solucionador SAT. Por exemplo, veja o artigo subsequente . Eles mostram que, em média, sua nova heurística CHB tem um desempenho melhor que o VSIDS. No entanto, se você observar atentamente a Tabela 1, verá que, em certos conjuntos de instâncias, a CHB realmente teve um desempenho pior em média ... Portanto, não acredito que falar sobre seja uma maneira saudável de seguir em frente. respondendo a esta pergunta. h e u r i s t i c sheuristicheuristics
Tayfun Pay
1
@ Martin, sem CDCL, obtemos apenas formas muito restritas de resolução (não me lembro exatamente do que estou pensando). Os resultados são de Paul Beame e outros que mostram que, com o CDCL e as reinicializações, você pode obter qualquer prova geral de resolução (no entanto, a seleção de pontos e ramificações de reinicialização é meio artificial), consulte o artigo de Beame para obter detalhes.
Kaveh
3
@ Martin, veja também a pesquisa de Jakob Nordstrom: csc.kth.se/~jakobn/project-proofcplx/docs/…
Kaveh
1
Em relação à complexidade da prova e ao CDCL, foi demonstrado por Pipatsrisawat e Darwiche sciencedirect.com/science/article/pii/S0004370210001669 e de forma independente por Atserias, Fichte e Thurley jair.org/papers/paper3152.html que o CDCL viu como um sistema de prova pode polinomialmente simule a resolução (os trabalhos apresentam resultados diferentes, mas as provas nos dois trabalhos podem ser usadas para obter os resultados no outro artigo). Uma diferença importante dos trabalhos anteriores nesta linha de pesquisa é que não há nada de articulação nesses modelos de CDCL. [Para ser continuado ...]
Jakob Nordstrom
17

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

Jakob Nordstrom
fonte
16

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.

Magnus Wahlström
fonte
2
Magnus, você definitivamente tem mais experiência nessa área do que qualquer outra pessoa que tentou responder a essa pergunta até agora. Quando afirmei "meus dois centavos", estava me referindo ao fato de que apenas estudei um grupo específico de problemas NP-Complete em minha dissertação e como os solucionadores de CSP e SAT tentam resolver as inúmeras instâncias desses problemas. Também tenho cerca de um ano de experiência no uso de solucionadores de CSP e SAT no local de trabalho, mas mais uma vez, isso não chega nem perto dos seus mais de 10 anos de experiência neste campo. Seus "dois centavos" provavelmente valem "duas pepitas de ouro". Uma questão.
Tayfun Pay
1
Você declara o seguinte em sua resposta "Não é verdade que os solucionadores SAT sejam universalmente bons para qualquer problema que você jogue em ....". Você conseguiu analisar a proporção de cláusulas para variáveis, c = m / n, para essas instâncias? Em outras palavras, eles estavam na região difícil, c = ~ 4,2 ou não? Como o que experimentei é que você acaba com muitas variáveis ​​quando reduz uma instância de CSP para uma instância de SAT, e geralmente é por esse motivo e não porque está realmente na região difícil, o solucionador de SAT leva mais tempo. hora de resolver.
Tayfun Pay
1
Por outro lado, se você sabe que essas instâncias acabaram na região difícil do SAT, c = ~ 4.2, então posso saber qual era esse problema da vida real? Eu estaria muito interessado em saber quais problemas da vida real realmente acabam na região difícil do SAT quando eles são reduzidos a ele. Obrigado
Tayfun Pay
2
Honestamente, tenho pouca ou nenhuma experiência na solução prática de SAT. Todo o meu trabalho real tem sido do lado da teoria pura dessa questão. Mas, seja como for, com relação à sua pergunta: Minha impressão é que os resultados para k-SAT aleatório e densidade de cláusulas (que você mencionou) realmente se aplicam apenas se a instância de entrada for literalmente uma fórmula aleatória uniforme. Observe também que o limite ~ 4.2 somente se aplica se a fórmula for 3-SAT, em oposição a uma fórmula CNF de comprimento misto.
Magnus Wahlström
1
E por "problemas não bem resolvidos pelos solucionadores de SAT", quero dizer principalmente problemas que se presume serem genuinamente intratáveis, como quebrar uma boa criptografia. No entanto, também existem fórmulas que nenhum solucionador de CDCL será capaz de resolver de maneira eficiente devido aos limites inferiores da teoria da prova, como as fórmulas principais do buraco do pombo. Eu vi pelo menos uma conversa com a mensagem "O solucionador de CDCL SAT falhou comigo", onde um pouco de escavação revela que o problema de codificação oculta um aspecto semelhante a um buraco de pombo (por exemplo, contendo alguma variação do problema de atribuição). Infelizmente, não me lembro dos detalhes.
Magnus Wahlström
15

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.

Jan Johannsen
fonte
Infelizmente, a resposta curta parece ser que realmente não há uma conexão clara e convincente com as medidas de complexidade de prova. Ainda pode haver correlações não triviais, mas parece que a teoria é muito limpa e a realidade é muito confusa para que haja uma combinação realmente boa. Em relação ao documento "Relating Proof Complexity Measures", descobriu-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 esperançosamente interessante.
Jakob Nordstrom
15

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.

Ryan O'Donnell
fonte
Sim. Random SAT e industrial SAT são jogos completamente diferentes, e os métodos utilizados são diferentes. Além disso, se você quiser resolver instâncias combinatórias realmente difíceis, outras técnicas serão mais bem-sucedidas (por exemplo, se o problema for difícil o suficiente, o aprendizado da cláusula não será realmente útil, exceto talvez localmente). Mas, de alguma forma, parece um equívoco bastante comum (pelo menos no lado aplicado da comunidade SAT) que a proporção de cláusulas para variáveis ​​deve de alguma forma ser relevante para qualquer instância do CNF SAT e não apenas para instâncias aleatórias.
Jakob Nordstrom