réduction polynomiale et co np complète

Question

J'aimerais savoir comment on peut démontrer ces deux problèmes :

• $A \leqslant_p B$ implique $\overline A \leqslant_p \overline B$
• Le complément de 3-SAT est co-NP-complet

Answer 1

Pour le premier, puisque $A \leq_p B$, il doit exister une fonction $f \in \operatorname{FP}$, tel que $x \en A$ si et seulement si $f(x) en B$ pour un mot arbitraire $x$.Nous pouvons prouver que $f$ est également une réduction de $\overline A$ à $\overline B$ comme suit:Soit x un mot arbitraire.begin {aligner} x in overline a & iff x notin a & iff f (x) notin b & iff f (x) in overline b & & qquad carré end {align}

Passons maintenant à la deuxième partie, nous savons que 3-SAT est NP-complet.Pour une langue donnée $A \in \operatorname{co-NP}$, laisser $B = \overline A$.Clairement $B \in \operatorname{NP}$ et donc il y a une réduction de $B$ à 3-SAT.Comme démontré ci-dessus, la même réduction est une réduction de $A$ au complément de 3-SAT.