Demostrar la completitud NP de la decidibilidad de la fórmula booleana monótona

12

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,

(x1x2)(x1x3)(x3x4x5)

es una función booleana monótona. Por otro lado, algo así como

(x1x2x3)(¬x1x3)(¬x1x5)

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 ?k1

Claramente, todas las variables podrían establecerse como positivas, y eso es trivial, por eso existe la restricción de variables definidas positivamente.k

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.¬x1z1x1z1

nat
fuente
¡Bienvenido! Tenga más cuidado con el idioma y el formato.
Raphael

Respuestas:

12

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.

(G,k)kG(ϕ,k)ϕ

La construcción básica:

vV(G)vvar(ϕ)vV(G)cv=uN(v)u

Un bosquejo de la prueba:

kkϕkcvv

Luke Mathieson
fuente
Wow, esto tiene mucho más sentido, ¡gracias! Creo que definitivamente estaba atrapado en tratar de reducir el SAT a la fórmula booleana monótona.
nat
También veo que también podemos reducir la cubierta del vértice a la fórmula booleana monótona.
nat
1
k
Creo que exactamente el mismo enfoque funciona con cobertura de vértices.
Haskell Fun
@ HaskellFun, también pensé en esto. La cubierta de vértice es la misma que la monótona Min-W2SAT.
rus9384
2

zi¬xiϕϕ¬xizixizikϕϕkxiziϕkk

david
fuente