A incorporação de uma solução é viável para o SAT?

10

Estou interessado em instâncias individuais "difíceis" de problemas de NP-completo.

Ryan Williams discutiu o problema SAT0 no blog de Richard Lipton . SAT0 pergunta se uma instância SAT tem a solução específica que consiste em todos os 0s. Isso me fez pensar em construir instâncias SAT que provavelmente serão "difíceis".

Considere uma instância SAT com cláusulas m e n variáveis, em que α = m / n é "grande o suficiente", no sentido de que se enquadra na região além da transição de fase, onde quase todas as instâncias são insatisfatórias. Seja x uma atribuição aleatória aos valores de ϕ .ϕmnα=m/nxϕ

É possível modificar para obter uma nova instância φ | x , para que ϕ | x é "amplamente semelhante" a ϕ , mas, portanto, x é uma atribuição satisfatória para ϕ | x ?ϕϕ|xϕ|xϕxϕ|x

Por exemplo, pode-se tentar adicionar a cada cláusula um literal escolhido aleatoriamente da solução, que ainda não ocorra na cláusula. Isso garantirá que é uma solução.x

Ou isso é inútil, levando a um algoritmo rápido para encontrar a solução "oculta", nos moldes do artigo recente a seguir?

Estou ciente da discussão de Cook e Mitchell e do trabalho que eles fazem referência. No entanto, não consegui encontrar nada sobre o que acontece com a estrutura de uma fórmula quando se tenta incorporar explicitamente uma tarefa satisfatória. Se isso é folclore, os ponteiros seriam muito bem-vindos!

  • Stephen A. Cook e David G. Mitchell, Encontrando Instâncias Difíceis do Problema da Satisfação: Uma Pesquisa , Série DIMACS em Matemática Discreta e Ciência da Computação Teórica 35 1–17, AMS, ISBN 0-8218-0479-0, 1997. ( PS )
András Salamon
fonte

Respostas:

13

Você pode pegar qualquer fórmula e alterá-lo para a fórmula φ ψ x , onde ψ x é uma instância de "hard" SAT cuja única solução é x . Uma maneira de construir essa fórmula é usar criptografia: se f : { 0 , 1 } n{ 0 , 1 } n é uma permutação unidirecional e escolhemos x aleatoriamente e definimos y = f ( x ) , então um pode converter y em uma fórmula SAT de modo que xφφψxψxxf:{0 0,1 1}n{0 0,1 1}nxy=f(x)yxé sua única solução e, portanto, encontrar corresponde à inversão de f . (Precisamos que esse x seja aleatório, mas algo semelhante é assumido de qualquer maneira, se acharmos que encontrar x deve ser difícil.)xfxx

Boaz Barak
fonte
Ah, tem tamanho polinomial em φ e ψ x . Obrigado! ϕψxϕψx
András Salamon
6

Se eu entendi corretamente o cerne da sua pergunta, você deseja tomar uma instância relativamente fácil (desde que se coloque em uma área em que ) e transforme-o em um difícil incorporando uma solução. Duvido que isso funcione.mn>4.3.

Dados experimentais sugerem que, ao construir uma instância aleatória "em torno de" uma solução predefinida , essa instância será mais fácil do que o habitual (em comparação com instâncias semelhantes com os mesmos n e m ). É como se a solução oculta ajudasse o solucionador SAT, guiando-o pelo espaço de pesquisa. Normalmente, para construir tal instância, geramos cláusulas aleatórias como de costume (por exemplo, escolhendo k literais aleatoriamente e negando cada uma delas com probabilidade p = 1xnmk ) mas descartamos as cláusulas que não são satisfeitas por nossa solução ocultax. Para o que diz respeito à sua abordagem de construçãoϕ| xde e instância difícilϕ: nunca tentei isso, mas "sinto" queϕ| xse tornará mais fácil, se não trivial. Acredito que isso aumentaria a contagem deocorrências dosliteraisdex(a contagemde ocorrências deum literallé o número de ocorrências delem uma determinada fórmula), e que isso levaria o solucionador SAT ao destino. Talvez os espaços de solução deϕeϕ| xp=1 12xϕ|xϕϕ|xxeueuϕϕ|xseria semelhante (se não quase idêntico), como acontece no exemplo de SAT0 de Ryan Williams (espaços de solução quase idênticos, mas dureza completamente diferente). Você tentou sua abordagem na prática? Seria interessante ver como o mesmo solucionador SAT se comporta em e em ϕ | x .ϕϕ|x

EDIT 1 (23 de setembro de 2010): Depois de pensar um pouco mais, sinto que realmente espaço da solução seria muito diferente do ϕ . Você está adicionando um literal a cada cláusula, para dar mais liberdade a essas cláusulas (ou seja, cada cláusula tem mais chances de ser satisfeita): provavelmente o espaço da solução resultante seria massivamente transformado.ϕ|xϕ

Edição 2 (1º de outubro de 2010): Pensei na seguinte idéia muito simples e não original. Dada uma instância inicial e uma atribuição x :ϕx

  1. Remova de todas as cláusulas não satisfeitas por x . Isso aumentará o espaço da solução e deve incorporar x nele.ϕxx

  2. Suponha que você tenha removido cláusulas. Agora adicione aleatoriamente m x novas cláusulas, cuidando para que elas não sejam satisfeitas por x (isso reduzirá o espaço da solução novamente, mas sem empurrar x para fora).mxmxxx

Não sei se isso vai funcionar ou não. Ainda não tentei. Mais precisamente, não tenho certeza se a Etapa 1 sempre consegue incorporar no espaço da solução (talvez x seja descartado por alguma combinação de cláusulas, mesmo que cada uma delas não seja insatisfeita com x ?).xxx

Giorgio Camerani
fonte
Obrigado pelos comentários, eu concordo que o espaço da solução seria alterado. Conforme indicado na pergunta, quero saber se existe uma maneira de modificar a fórmula para ocultar uma solução. Adicionar os literais a cada cláusula significa uma prova de existência de que se pode adicionar a solução à fórmula. Não pretendia sugerir que esse é o único, melhor ou até um bom método.
András Salamon
De nada, Andras. Sim, certamente a solução pode ser adicionada usando seu método. Se você quiser que o & Phi; | x 's espaço de solução é exatamente igual ao φ espaço solução mais apenas que a solução x , eu acho que isso é difícil de obter. Por outro lado, se você estiver disposto a aceitar que muitas outras soluções serão adicionadas, sua estratégia está correta. xϕ|xϕx
Giorgio Camerani
Idealmente quer um método polytime-computável que não altera o espaço de solução "muito" ...
András Salamon
Seria interessante verificar se o algoritmo mencionado por Feige para cliques plantados ainda funciona para qualquer uma dessas soluções plantadas. n3registro n
András Salamon
@ Walter: A razão pela qual digo que seria interessante investigar o algoritmo simples "encontrar um log logique" é que a redução mais fácil de SAT para CLIQUE exige um n- clique em um gráfico com 2 n vértices. Seria interessante preencher essa lacuna entre n e 3 log n , ou mostrar que ela não pode ser preenchida. 3registronn2nn3registron
András Salamon
4

A melhor maneira de gerar instâncias concretas de problemas de NP-completos que eu conheço é usar o mapeamento Cook para reduzir instâncias cuidadosamente selecionadas de outros problemas de NP rígidos (como o problema de logaritmo discreto ou fatoração de número inteiro) para SAT. Esses são os mesmos "problemas difíceis" usados ​​pelos matemáticos para garantir a segurança criptográfica em protocolos como RSA e Diffie-Hellman.

Philip White
fonte
Referências, por favor?
Gphilip
não sei por que o voto negativo para esta resposta. quem fez isso deve explicar.
Suresh Venkat