Max 2-SAT es el tiempo polinomial reducible a 2-SAT?

Question

Sé que 2-SAT es solucionable en tiempo polinomial y 2-SAT es NP-HARD.

Tengo problemas sobre esta declaración: MAX 2-SAT es el tiempo de polinomio reducible a 2-SAT.¿Puedes explicarme cómo se ve la reducción?Necesito la única intención sobre eso, pero no a prueba.

Answer 1

Creo que hay cierta confusión aquí.Max-2-SAT es NP-HARD (y su versión de decisión es NP-Completa), mientras que 2-SAT está en P y, por lo tanto, también en NP.Esto significa que 2-SAT es reducible de tiempo polinomial para (la versión de decisión de) Max-2-SAT.Lo contrario no es cierto a menos que p= np.

Let $ \ phi $ Sea una fórmula de 2 satélites con $ m $ cláusulas. Si realmente desea reducir una instancia $ \ phi $ de 2-SAT a (la versión de decisión de) Max-2-SAT, entonces esto simplemente canta para verificar sial menos $ M $ (es decir, todas) cláusulas de $ \ phi $ son satisfechos.