Max 2-SAT è il tempo polinomiale riducibile a 2-SAT?

Question

So che 2-SAT è solvibile in tempo polinomiale e 2-SAT è difficile.

Ho un problema su questa affermazione: Max 2-SAT è riducibile in polinomiale a 2 sab.Puoi spiegarmi come appare la riduzione?Ho bisogno dell'unica inquistabilità a riguardo, ma non prova.

Answer 1

Penso che ci sia qualche confusione qui.Max-2-SAT è NP-Hard (e la sua versione decisionale è NP-completa), mentre 2-SAT è in P e quindi anche in NP.Ciò significa che 2-SAT è riducibile in polinomiale (la versione decisionale di) Max-2-SAT.Il Converse non è vero a meno che P= NP.

Let $ \ phi $ essere una formula a 2 satelliti con $ m $ clausole. Se vuoi davvero ridurre un'istanza $ \ phi $ di 2-SAT a (la versione decisionale di) max-2-sat, quindi questo è semplicemente per il controllo seAlmeno $ m $ (cioè, tutte) clausole di $ \ phi $ sono soddisfatti.