Tentar encontrar a solução ideal para o WEIGHTED-MAX-3SAT, a versão ponderada do problema de otimização do 3-SAT, é difícil para o NP. De fato, mesmo aproximando-se arbitrariamente da versão não ponderada do MAX-SAT é comprovadamente difícil o NP pelo Teorema do PCP.
Um algoritmo canônico para aproximar o WEIGHTED-MAX-3SAT é o MAX-WalkSAT. Olhando em volta, encontrei algumas informações sobre outros algoritmos (por exemplo, branch-and-bound, o algoritmo DPL) que são comumente usados para encontrar soluções para o 3-SAT ou o MAX-3SAT (não ponderado), mas não vi nenhuma discussão sobre como bem, estes funcionariam para a versão ponderada. Intuitivamente, sem serem adaptados, eles não funcionariam tão bem.
Pergunto-me que outros algoritmos são comumente usados para aproximar o WEIGHTED-MAX-SAT, se existem conhecidos solucionadores do WEIGHTED-MAX-SAT e a qualidade relativa desses algoritmos / solucionadores.
fonte
Respostas:
Bem, isso pode ser formulado como o problema de encontrar o estado fundamental de um hamiltoniano do tipo Ising, com termos locais 3. Isso não ocorre naturalmente, mas você esperaria que eles esfriassem de maneira semelhante a outros sistemas; portanto, o recozimento simulado deve funcionar bem para a versão ponderada.
fonte
Eu acho que é possível fazer redução simplesmente duplicando as fórmulas de acordo com seu peso e, portanto, os resultados dos limites superior e inferior para o 3-SAT não ponderado também se aplicam às versões ponderadas, com perdas arbitrariamente pequenas. E, de acordo com um resultado clássico de Johan Håstad, é NP-difícil aproximar o 3-SAT além de 7/8, que é o desempenho de atribuir valores aleatórios.
Não tenho certeza sobre o desempenho dos algoritmos usados na prática.
fonte