Max 2-Sat é tempo polinomial redutível para 2-SAT?

Question

Eu sei que 2-SAT é solucionável no tempo polinomial e 2-SAT é NP-Hard.

Eu tenho problema sobre esta afirmação: Max 2-Sat é o tempo de polinomial reduzido a 2-SAT.Você pode me explicar como é a redução?Eu preciso da única intuição sobre isso, mas não prova.

Answer 1

Eu acho que há alguma confusão aqui.O Max-2-Sat é NP-HARD (e sua versão de decisão é NP-COMPLE), enquanto 2-SAT estão em p e, portanto, também no NP.Isso significa que 2-SAT é o tempo polinômio redutível para (a versão de decisão do) Max-2-Sat.O inverso não é verdade, a menos que p= np.

Deixe $ \ phi $ ser uma fórmula de 2 sat com $ m $ cláusulas. Se você realmente quer reduzir uma instância $ \ phi $ de 2-SAT para (a versão de decisão do) Max-2-Sat, então isso simplesmente equivale a verificar sePelo menos $ m $ (isto é, tudo) cláusulas de $ \ phi $ são satisfatórios.