Estoy tratando de resolver este problema y realmente estoy luchando.
Una fórmula booleana monótona es una fórmula en lógica proposicional donde todos los literales son positivos. Por ejemplo,
es una función booleana monótona. Por otro lado, algo así como
no es una función booleana monótona.
¿Cómo puedo demostrar que NP está completo para este problema?
¿Determinar si una función booleana monótona es satisfactoria si variables o menos se establecen en 1 ?
Claramente, todas las variables podrían establecerse como positivas, y eso es trivial, por eso existe la restricción de variables definidas positivamente.
He intentado una reducción de SAT a fórmula booleana monótona. Una cosa que he intentado es sustituir una variable ficticia por cada literal negativo. Por ejemplo, traté de reemplazar con z 1 , y luego intenté forzar a x 1 y z 1 a tener valores diferentes. Sin embargo, no he podido hacer que esto funcione.
Respuestas:
El "padre" del problema que está viendo a veces se llama Satisfabilidad ponderada (WSAT, particularmente en la complejidad parametrizada) o Min-Ones (aunque esta es normalmente una versión de optimización, pero lo suficientemente cerca). Estos problemas tienen la restricción "como máximo variables establecidas en verdadero" como su característica definitoria.k
La restricción a las fórmulas monótonas es en realidad sorprendentemente fácil de mostrar dureza, solo necesita resolver los problemas de satisfacción por un momento. En lugar de intentar modificar una instancia de SAT, comenzamos con Dominating Set (DS).
A ver si puedes conseguirlo desde allí. Hay más en los spoilers, divididos en pedazos, pero evítalos si puedes. No mostraré membresía en NP, no deberías tener ningún problema con eso.
La construcción básica:
Un bosquejo de la prueba:
fuente
fuente