¿Cuál es la complejidad de y ? ¿Están en P? ¿Son NP-hard?
Para formalizar esto más precisamente, dejemos
donde y cada cláusula tiene la forma o .
El problema es encontrar una asignación a que satisfaga . Este problema está en , ya que corresponde a un sistema de ecuaciones lineales mod .
El problema de es encontrar una asignación a que maximice el número de cláusulas que se satisfacen. El problema es encontrar una asignación a que minimice el número de cláusulas que se satisfacen. ¿Cuáles son las complejidades de estos problemas?
¿Está inspirado en MIN o MAX-True-2-XOR-SAT NP-hard?
Si todos los vértices de la gráfica se pueden colorear con 2 colores y ninguno de los dos vértices con un borde compartido común tiene asignado el mismo color, entonces la ecuación es satisfactoria.
Pero un gráfico es de 2 colores si es un gráfico bipartito. Y determinar si un gráfico es bipartito se puede hacer en tiempo polinómico. Por lo tanto, el problema está en P, porque si podemos determinar en tiempo polinómico que el gráfico es un gráfico bipartito, entonces es solucionable, de lo contrario no es solucionable.
fuente