Max 2-SAT est une période polynomiale réductible à 2-sat?

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.

Answer 1

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.