MaxSat usando algoritmo DPLL?

Question

É possível retornar de um algoritmo Dpll m como o máximo para o problema Max-Sat?:

Eu tenho uma amostra:

https://gist.github.com/davefernig/e670bda722d558817f2BA0E90Ebce66f

Podemos modificar a recorrência para retornar o resultado do Max-Sat?

Recursos: https://en.wikipedia.org/wiki/dpll_algorithm

Answer 1

O algoritmo DPLL não tenta satisfazer tantas cláusulas quanto possível.Se houver uma tarefa satisfatória, o DPLL achará.Caso contrário, a DPLL tentará uma série de tarefas parciais até ficar sem possibilidades e, em seguida, declarará a fórmula insatisfatória.Mas no caso de uma fórmula insatisfável, não há garantia de que a DPLL descubra o número máximo de cláusulas satisfatórias no caminho para provar insenestibilidade.

O problema do MaxSat está relacionado ao encontrar as subformulas minimamente insatisfeitáveis (musas) de uma instância.Determinando se um conjunto de cláusulas é um mus é um problema completo de DP.Espera-se que isso seja mais difícil do que mera completude NP, portanto, é improvável que modifique a DPLL para retornar soluções parciais.Dado que a classe DP está contida na $ \ delta ^ p_2 $ Você pode conceber um esquema que chama o DPLL (ou algoritmos relacionados) um número polinômico de vezes para produzir um MaxSatresultado.