\documentclass{article} \usepackage[utf8]{inputenc} \usepackage[T1]{fontenc} \usepackage[french]{babel} \usepackage[top=2cm, bottom=2cm, left=2cm, right=2cm]{geometry} \usepackage{xcolor} \usepackage{tabto} \usepackage{amsmath} \usepackage{amssymb} \usepackage{ulem} \usepackage{graphicx} \title{Algo 2 : TD 2 : Np-complétude} \author{Yoann \bsc{Lemesle} && Mathieu \bsc{Chambard}} \date{11 février 2020} \begin{document} \maketitle \newpage \section{3-SAT} On souhaite montrer que 3-SAT est NP-complet.\\ Le problème 3-SAT est défini comme suit. \\ Instance : Une formule $\Phi$ du calcul propositionnel en forme normale conjonctive dont chaque clause possède au plus 3 littéraux. \\ Question : La formule $\Phi$ est-elle satisfiable,ie peut-on trouver une valuation $\nu$ des variables de $\Phi$ qui la rende vraie ? \\ \subsection*{1.1 Montrer que 3-SAT est dans NP} \subsection*{Correction :} Pour montrer cela, on va prendre une valuation $\nu$ et l'on va montrer que l'on peut vérifier qu'elle répond ou non au problème 3-SAT (cad satisfait-elle $\Phi$ ou non ) en un temps polynomial.\\ La formule $\Phi$ du calcul propositionnel est sous la forme normale conjonctive donc on a :\\ $\Phi = \bigwedge \limits_{i =1}^n {(a_{i,1} \lor a_{i,2} \lor a_{i,3})}$ \\ Or étant donnée une valuation $\nu$, chaque clause de $\Phi$ doit être vérifié. Au pire des cas, on doit vérifier les 3 variables propositionnelles. Donc on a, au pire des cas, 3*n comparaisons. \\ La vérification de cette valuation $\nu$ pour le problème 3-SAT a une compléxitée dans le pire des cas en O(n). \\ Le problème 3-SAT est donc bien NP.\\ \\ \\ \\ \\ On souhaite maintenant trouver une transformation polynomiale de SAT vers 3-SAT. \subsection*{1.2 Soit C une clause contenant 2 littéraux. En introduisant une nouvelle variable, transformer C en une conjonction $C_{1} \wedge C_{2}$ de clauses contenant 3 littéraux et telle que C et $C_{1} \wedge C_{2}$ sont équisatisfiables.} \subsection*{Correction :} On a C une clause de 2 littéraux donc $ C = p \vee q$. \\ On pose $C' = (p \vee q \vee i) \land (p \vee q \vee \neg i)$. \\On va montrer que C et C' sont équisatisfiables et que les mêmes valuations les rendent vrai. \\ ($\Rightarrow$)Pour cela, on prend une valuation qui satisfait C : on a donc p ou q a vrai et donc $(p \vee q \vee i)$ est à vrai et $(p \vee q \vee \neg i)$ est à vrai et finalement C' est à vrai. On a donc trouvé une valuation qui satisfait C' \\ ($\Leftarrow$) On prend un valuation $\nu$ qui rend C' vrai. \\ Si i = vrai, on sait que $(p \vee q \vee \neg i)$ est vrai donc $(p \vee q)$ est vrai car $\neg i$ est faux. \\ Sinon, on sait que $(p \vee q \vee i)$ est vrai donc $(p \vee q)$ est vrai car $i$ est faux Donc cette valuation satisfait C. \\ On a donc prouvé que C et C' sont équisatisfiables. \subsection*{1.3 Soit $k \ne 4$ et C une clause contenant k littéraux. En introduisant k-3 nouvelles variables, transformer C en une conjonction $C_{1} \wedge ... \wedge C_{k-2}$ de clauses contenant 3 littéraux et telle que C et $C_{1} \wedge ... \wedge C_{k-2}$ sont équisatisfiables.} \subsection*{Correction :} C est cette fois-ci de la forme $ C = l_{1} \vee ... \vee l_{k} $. J'introduis les k-3 variables suivantes : $ p_{1},...,p_{k-3}$ et je pose : $ C' = (l_{1} \vee l_{2} \vee p_{1}) \bigwedge \limits_{i =3}^{k-2} {(l_{i} \vee \neg p_{i-2} \vee p_{i-1})} \wedge (\neg p_{k-3} \vee l_{k-1} \vee l_{k})$ \\ On montre que C et C' sont équisatisfiables : \\ ($\Rightarrow$) On prend une valuation $\nu$ qui satisfait C. \\ $ \exists j \in [|1,k|] $ tel que $l_{j}$ est vrai. On met $p_{1}$,..,$p_{j-2}$ à Vrai et $p_{j-1}$,...,$p_{k-3}$ à Faux. Je dis que cette nouvelle valuation $\nu'$ satisfait C'. Je le montre : \\ Si j = 1,2 alors $(l_{1} \vee l_{2} \vee p_{1})$ est vrai et on met tout les $p_{i}$ à Faux et le reste est vrai car chaque clause à un $\neg p_{i}$.\\ Si j = k-1,k alors $(\neg p_{k-3} \vee l_{k-1} \vee l_{k})$ est vrai et on met tout les $p_{i}$ à Vrai et le reste est vrai car chaque clause à un $p_{i}$.\\ Sinon on a $(l_{j} \vee \neg p_{i-2} \vee p_{i-1})$ qui est vrai et on met $p_{1}$,..,$p_{j-2}$ à Vrai donc $(l_{1} \vee l_{2} \vee p_{1})$ est vrai et toutes les clauses $(l_{i} \vee \neg p_{i-2} \vee p_{i-1})$ pour i allant de 3 à j-1 sont vrai grâce à $p_{i-1}$. De plus, on met $p_{j-1}$,..,$p_{k-3}$ à Faux donc $(\neg p_{k-3} \vee l_{k-1} \vee l_{k} )$ est vrai et toutes les clauses $(l_{i} \vee \neg p_{i-2} \vee p_{i-1})$ pour i allant de j+1 à k-2 sont vrai grâce à $\neg p_{i-2}$. \\ Donc cette nouvelle valuation satisfait C'.\\ ($\Leftarrow$) Soit $\nu$ une valuation qui satisfait C'. On va montrer qu'il existe un $l_{i}$ qui est vrai.\\ Pour cela, on suppose qu'il n'y a pas de $l_{i}$ à vrai. C' est donc équivalent à $p_{1} \bigwedge \limits_{i =3}^{k-2} {(\neg p_{i-2} \vee p_{i-1})} \wedge \neg p_{k-3}$. Donc $p_{1}$ est vrai et C' est donc équivalent à $p_{2} \bigwedge \limits_{i =4}^{k-2} {(\neg p_{i-2} \vee p_{i-1})} \wedge \neg p_{k-3}$ Donc $p_{2}$ est vrai et de proche en proche on a $p_{k-3}$ qui est vrai. Or la dernière clause est $\neg p_{k-3}$ et elle est vrai. C'est absurde !! \\ On a donc qu'il existe i tel que $l_{i}$ est vrai. Donc la valuation satisfait C.\\ On a donc que C et C' sont équisatisfiables. \subsection*{1.4 Conclure quant à la complexité du problème 3-SAT} \subsection*{Correction :} La question 1.3 nous donne une réduction du problème SAT vers 3-SAT. \\ On prend une formule $\Phi$ du calcul propositionnel en forme normale conjonctive. On regarde chaque clauses. Pour chaque clauses C, on pose k le nombre de littéraux de celle-ci. Avec la question 1.3, on peut transformer le problème de satisfiabilité de cette clause C en un problème de satisfiabilité d'un problème 3-SAT. Donc pour chaque clause C, on la transforme en k-2 clauses de 3 littéraux. \\ On a donc une réduction en un temps polynomial d'un problème SAT vers un problème 3-SAT. Or le problème SAT est un problème NP-difficile donc 3-SAT est un problème NP-difficile. Or 3-SAT est NP donc 3-SAT est un problème NP-complet.\\\\\\ \section{MAX2SAT} Dans cet exercice, on souhaite prouver que le problème MAX2SAT est NP-Complet. Ce problème est défini ainsi : \\ Instance : Une formule $\Phi$ du calcul propositionnel en forme normale conjonctive dont chaque clause possède au plus 2 littéraux, et un entier k. \\ Question : La formule $\Phi$ est-elle k-satisfiable,ie peut-on trouver une valuation $\nu$ des variables de $\Phi$ qui rende k clauses de $\Phi$ vraies ? \\ \subsection*{2.1 Etudier la satisfaction des clauses de $\Phi'$ en fonction de celle des clauses de $\Phi$} \subsection*{Correction :} Chacune des clauses ($\textrm{a}_\textrm{i}$ $\vee$ $\textrm{b}_\textrm{i}$ $\vee$ $\textrm{c}_\textrm{i}$) de $\varphi$ est satisfaite si un littéral ou plus parmis \{$\textrm{a}_\textrm{i}$, $\textrm{b}_\textrm{i}$, $\textrm{c}_\textrm{i}$\} est vrai. \medbreak \underline{$\rightarrow$ 1 littéral vrai : $L_1$} \medbreak \par $\bullet$ Les 3 clauses ($\neg$X $\vee$ $\neg$Y) sont vraies car il ne peut pas exister de couple (X,Y) de littéraux vrais. \par $\bullet$ Une des clauses ($a_i$) , ($b_i$) , ($c_i$) est vraie. \par $\bullet$ $d_i$ vrai : ($d_i$) et ($L_1$ $\vee$ $\neg$$d_i$) vraies $\rightarrow$ 5 clauses satisfaites. $d_i$ faux : les 3 clauses (X $\vee$ $\neg$$d_i$) sont vraies $\rightarrow$ 7 clauses satisfaites. \medbreak \underline{$\rightarrow$ 2 littéraux vrais : $L_1$ et $L_2$} \medbreak \par $\bullet$ Seule une des 3 clauses ($\neg$X $\vee$ $\neg$Y) est fausse, quand (X,Y) = ($L_1$, $L_2$), 2 clauses sont dont satisfaites. \par $\bullet$ Deux des clauses ($a_i$) , ($b_i$) , ($c_i$) sont vraies. \par $\bullet$ $d_i$ vrai : ($d_i$) , ($L_1$ $\vee$ $\neg$$d_i$) et ($L_2$ $\vee$ $\neg$$d_i$) vraies $\rightarrow$ 7 clauses satisfaites. $d_i$ faux : les 3 clauses (X $\vee$ $\neg$$d_i$) sont vraies $\rightarrow$ 7 clauses satisfaites. \medbreak \underline{$\rightarrow$ 3 littéraux vrais} \medbreak \par $\bullet$ Toutes les clauses ($\neg$X $\vee$ $\neg$Y) sont fausses. \par $\bullet$ Les 3 clauses ($a_i$) , ($b_i$) , ($c_i$) sont vraies. \par $\bullet$ $d_i$ vrai : ($d_i$) , ($a_i$ $\vee$ $\neg$$d_i$) , ($b_i$ $\vee$ $\neg$$d_i$) et ($c_i$ $\vee$ $\neg$$d_i$) vraies $\rightarrow$ 7 clauses satisfaites. $d_i$ faux : les 3 clauses (X $\vee$ $\neg$$d_i$) sont vraies $\rightarrow$ 6 clauses satisfaites. \medbreak Dans tous les cas, pour une clause satisfaite de $\varphi$, 7 clauses de $\varphi$' sont satisfiables car $d_i$ n'est pas fixé par \par la valuation qui satisfait ($a_i$ $\vee$ $b_i$ $\vee$ $c_i$). Si $\varphi$ contient P clauses vraies, alors $\varphi$' contient 7 * P clauses \par satisfiable. \medbreak \subsection*{2.2 Proposer une valeur de k telle que $\Phi$ est satisfiable si et seulement su k clauses de $\Phi'$ sont simultanément satisfiables.} \subsection*{Correction :} Pour une formule $\varphi$ à P clauses, on propose k = 7 * P. \medbreak \subsection*{2.3 Montrons que MAX2SAT est NP-complet.} \subsection*{Correction :} \medbreak \par Un verificateur pour MAX2SAT prend en entrée une instance du problème (une formule normale conjonctive dont les clauses contiennent au plus 2 littéraux, un entier k) et une valuation. Vérifier que cette valuation rend vraies au moins k clauses se fait en temps polynomial sur le nombre de clause, avec une complexité temporelle constante pour chaque clause (du fait du nombre borné de littéraux). \medbreak MAX2SAT appartient donc bien à la classe des problèmes NP.\\ \par Montrons que MAX2SAT $\in$ NP-Difficile : \medbreak \par Soit une formule $\varphi$ 3-CNF, transformons la en une formule $\varphi$' via le procédé définit par l'énoncé. \\ On applique à $\varphi$' le problème MAX2SAT avec k = 7*P, P le nombre de clauses de $\varphi$'.\\ D'après 2.2, si le résultat est positif pour 7*P, alors la formule $\varphi$ est satisfiable, ce qui répond au problème 3-SAT.\\ Ainsi, le problème 3-SAT se réduit au problème MAX2SAT. Or 3-SAT est NP-Difficile, il en est donc de même pour MAX2SAT. \medbreak MAX2SAT est NP et NP-Difficile, il est donc NP-Complet. \section{Couverture par sommets :} On définit le problème de la couverture par sommets d'un graphe \\ Instance : Un graphe non orienté G = (V,E), un entier naturel k \\ Question : Le graphe G admet-il une couverture par k sommets, i.e. existe-t-il $V' \subseteq V$, avec $|V'| \leq k $ tel que $\forall \{u,v\} \in E, u \in V' \vee v \in V'$ \subsection*{3.1 Montrons que VC est dans NP.} \subsection*{Correction :} Soit V' un ensemble de sommets. On doit vérifier si cet ensemble recouvre notre graphe. Pour cela, On prend chaque arrête et on vérifie que un de ces sommets est dans V'. \\ On a donc au maximum 2 * |V'| * |A| comparaisons( |V'| est pour vérifier que le sommet est dans V' ). La vérification est donc bien en temps polynomial. \\ Le problème VC est donc bien dans NP. \subsection*{3.2 Construire G et exhiber une couverture minimale de G.} \subsection*{Correction :} \begin{center} \includegraphics[scale=0.5]{./fig1.png} \end{center} \begin{center} \includegraphics[scale=0.5]{./fig2.png} \end{center} \end{document}