Max 2-SAT est une période polynomiale réductible à 2-sat?
-
29-09-2020 - |
Question
Je sais que 2-SAT est résoluble en temps polynomial et 2-sat est le NP-dur.
J'ai une question à propos de cette déclaration: Max 2-SAT est un temps polynomial réductible à 2-sat.Pouvez-vous m'expliquer comment on ressemble de la réduction?J'ai besoin de la seule intuition à ce sujet, mais pas de preuve.
La solution
Je pense qu'il y a une certaine confusion ici.Max-2-SAT est NP-HARD (et sa version de décision est NP-Complete), tandis que le 2-SAT est en P et donc dans NP.Cela signifie que la 2-SA sat est réductible en polynôme à (la version de décision de) max-2-sat.L'inverse n'est pas vrai sauf si p= np.
let $ \ phi $ soit une formule de 2-sat avec $ M $ clauses. Si vous voulez vraiment réduire une instance $ \ Phi $ de 2-SAT à (la version de décision de) max-2-sat, alors cela équivaut simplement à vérifier siau moins $ M $ (c.-à-d. Tous) clauses de $ \ phi $ sont satisfiables.