Complejidad de casos específicos de max2sat

Question

Sé que Max2SAT es NP-Completa en general, pero me pregunto si se sabe que algunos casos restringidos están en P. Ciertamente, los idiomas

$ l_k:=\ \ \ phi \, | \, \ phi \, \ text {es una instancia de 2sat, que tiene una asignación que satisface al menos k cláuses.} } $

se puede resolver en $ o (n ^ k) $ a través de la búsqueda de fuerza bruta desde cada idioma $ k $ es fijo. Sin embargo, me estoy preguntando sobre el caso cuando se especifica una fracción de las cláusulas. ¿Alguna fracción produce un problema de NP? Específicamente, me estoy preguntando sobre el caso de satisfacer al menos la mitad de las cláusulas de una instancia de 2SAT.

La reducción que vi a partir de 3SAT a MAX2SAT Construye 10 cláusulas de cada cláusula en 3SAT de tal manera que de estos diez, exactamente 7 se cumplen cuando la cláusula 3SAT original está satisfecha y, a su mayoría, 6 se satisfacen cuando la cláusula original no está satisfecha . Entonces, en esta reducción, la fracción de $ 7/10 $ funciona pero $ 1/2 $ no hace falta de verdad Las asignaciones de una instancia de 3SAT aún pueden producir una instancia de 2SAT que tiene una asignación que satisface más de la mitad de las cláusulas. Pensé en otra construcción o agregando cláusulas adicionales a una instancia de 2SAT, pero no he tenido éxito hasta ahora.

Answer 1

Siempre puede satisfacer al menos la mitad de las cláusulas: para cada variable $ x $ , encuentre el número de cláusulas que contienen $ x $ y la cantidad de cláusulas que contienen $ \ lnot x $ . Seleccione el que satisfaga la mayoría de las cláusulas. Retire las cláusulas que contienen $ x $ y $ \ lnot x $ . Repita para otras variables.

Dado que para cada $ x $ Satisfacemos al menos la mitad de las cláusulas eliminadas, satisfacemos la mitad de las cláusulas en general.

Por otro lado, también está apretado: deje que $ \ alfa> \ frac 12 $ sea la fracción de cláusulas para las cuales podemos dar una respuesta. Deje que $ \ beta> \ frac 12 $ sea la fracción máxima de cláusulas que podemos satisfacer en una cláusula específica. Luego podemos agregar cláusulas para que $ \ beta $ (para la nueva cláusula) se convierte en una cláusula arbitraria en $ \ alfa $ < / SPAN>:

• si $ \ beta <\ alfa $ , entonces podemos agregar cláusulas $ (x_i \ lor \ lnot x_i) $ , hasta $ \ beta> \ alfa $ (ya que estas cláusulas son siempre verdaderas, $ \ beta $ aumenta).
• si $ \ beta> \ alfa $ , podemos agregar cláusulas $ (x_i) $ y $ (\ lnot x_i) $ , hasta $ \ beta <\ alfa $ (desde exactamente la mitad de las cláusulas es cierto, $ \ beta $ disminuye).

No chequeo, sino para obtener $ o (\ frac 1 m) $ diferencia (es decir, para encontrar el número exacto de cláusulas), creo que es suficiente Para agregar $ o (m) $ cláusulas. En otras palabras, si podemos resolver para un poco de $ \ alfa> \ frac 12 $ , podemos buscar cualquier $ \ beta $ si $ \ beta $ se puede satisfacer la fracción de cláusulas y, por lo tanto, podemos resolver max2sat en tiempo polinomial.