Maxsat usando el algoritmo DPLL?

Question

¡Es posible volver de un algoritmo DPLL M como máximo para el problema Max-SAT?:

Tengo una muestra:

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

Podemos modificar la recurrencia para devolver el resultado de Max-SAT?

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

Answer 1

El algoritmo DPLL no intenta satisfacer la mayor cantidad posible de cláusulas.Si hay una tarea satisfactoria, DPLL lo encontrará.De lo contrario, DPLL intentará una serie de asignaciones parciales hasta que se quede sin posibilidades, y luego declarará la fórmula insatisfactoria.Pero en el caso de una fórmula insatisfiable, no hay garantía de que DPLL descubra el número máximo de cláusulas satisfactorias en la forma de demostrar la insatisfacia.

El problema de MaxSat está relacionado con la búsqueda de subformulas mínimamente insatisfactiles (MUSES) de una instancia.Determinar si un conjunto de cláusulas es un MUS es un problema completo de DP.Se espera que esto sea más difícil que la mera integridad de NP, por lo que es poco probable que la modificación de DPLL para devolver las soluciones parciales será fructífera.Dado que la clase DP está contenida en $ \ delta ^ p_2 $ Puede diseñar un esquema que llama a DPLL (o algoritmos relacionados) un número polinomio de veces para producir un MaxSatresultado.