\documentclass{scrartcl}
\usepackage[margin=1in, left=0.5in, right=0.5in]{geometry}
\usepackage[utf8]{inputenc}
\usepackage[francais]{babel}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{fancyhdr}
\usepackage{mathtools}
\usepackage{graphicx}
\usepackage{subcaption}
\fancyhead[R]{\textsc{Langage formels, calculabilité et complexité}}
\fancyhead[L]{TD8} % except the center
\fancyfoot{} % except the center
\fancyfoot[L]{louis.jachiet@ens.fr}
\fancyfoot[C]{https://louis.jachiet.com/tps.html}
\fancyfoot[R]{7 décembre 2017}
\newcommand{\DP}{\mathcal{P}}
\newcommand{\NP}{\mathcal{NP}}
\newcommand{\coNP}{\mbox{co-}\mathcal{NP}}
\newcommand{\B}{\mathcal{B}}
\newcommand{\X}{\mathcal{X}}
\newcommand{\I}{\mathcal{I}}
\newcommand{\F}{\mathcal{F}}
\newcommand{\R}{\mathcal{R}}
\newcommand{\Ls}{{\mathcal{L}_\Sigma}}
\newcommand{\Lc}{{\mathcal{L}}}
\newcommand{\ml}{\mu_{\mathcal{L}}}
\newcommand{\Mn}{M_n(\Ls)}
\newcommand{\Vn}{{M_{n,1}(\Ls)}}
\newcommand{\tr}[1]{\xrightarrow{#1}}
\newcommand{\td}{\tilde{\delta}}
\newcommand{\norm}[1]{\left\lvert#1\right\rvert}
\newcommand{\code}[1]{{\langle}{#1}{\rangle}}
\renewcommand{\headrulewidth}{0.4pt}
\renewcommand{\footrulewidth}{0.4pt}
\usepackage{exsheets}[2014/09/14] % v0.16 or newer
\SetupExSheets{
  headings = runin ,
  headings-format = \large\bfseries\sffamily ,
  subtitle-format = \large\bfseries\sffamily ,
%  counter-within = section ,
%  counter-format = se.qu\IfQuestionSubtitleT{:} ,
%solution/print = true
}
\newtheorem{defi}{Définition}

\newcommand\myeq{\stackrel{\mathclap{\normalfont\mbox{def}}}{=}}

\newcommand*\fo[1]{\tikz[baseline=(char.base)]{
                \node[shape=circle,draw,inner sep=2pt] (char) {#1};}}
\usepackage{tikz}
\usetikzlibrary{automata,positioning,trees}

\author{}
%\date{}
\title{TD8 : Langages formels, calculabilité et complexité}

\begin{document}
\pagestyle{fancy}

\section{Réduction de 3-SAT à CNF-SAT}


Une formule \emph{CNF} (pour \emph{Conjunctive Normal Form}) est la
donnée d'un ensemble de variables $x_1, \dots, x_n$ et d'un ensemble
de clauses $C_1, \dots, C_k$ où chaque clause est une disjonction de
littéraux (un littéral est soit une variable $x_i$ soit la négation
d'une variable $\lnot x_i$). Pour tout $1\leq j \leq k$, on a donc
$C_j = \bigvee_i v^j_i$ où $v^j_i = x_l$ ou $v^j_i=\lnot x_l$ pour un
certain $l$.

Une formule CNF est satisfiable s'il existe une assignation des
variables $x_1, \dots, x_n$ à vrai ($\top$) ou faux ($\bot$) telle que
chaque clause soit satisfaite (c'est à dire que pour chaque clause au
moins un de ses littéraux est vrai). Du point de vue logique une
formule CNF est donc une formule de la forme :
$\exists x_1, \dots x_n\in \{\top,\bot\}^n: {\bigwedge_j \left( \bigvee_{i} v^j_i \right)}$.

\begin{defi}
Le problème \emph{CNF-SAT} est celui de décider si une formule CNF est
satisfiable.
\end{defi}


\begin{defi}
Le problème $k$\emph{-SAT} est le problème CNF-SAT où l'on impose que
chaque clause contienne au plus $k$ littéraux.
\end{defi}


\begin{question} 
Montrer que les problèmes \emph{CNF-SAT} et \emph{$k$-SAT} (pour tout
$k\in\mathbb{N}$)) sont dans $\NP$.
\end{question}

\begin{solution}
On considère comme certificat la valuation de chacune des
variables. Vérifier la valuation est faisable en temps polynomial.
\end{solution}

\begin{question}
Montrer que la formule $(v_1\lor v_2\lor v_3\lor v_4)$ est satisfaite
seulement quand il existe $l$ tel que $(v_1\lor v_2\lor l) \land
(\lnot l \lor v_3\lor v_4)$ est aussi satisfaite (où $l$ est une
variable qui n'apparaît pas dans les littéraux
$v_1, \dots, v_4$).
\end{question}

\begin{solution}
  Soit $(v_1\lor v_2 \lor v_3 \lor v_4)$ est satisfiable alors l'un
  des $v_1, \dots, v_4$ est vrai. Si $v_1$ ou $v_2$ est vrai alors
  $l=\bot$ rend la second formule satisfiable, sinon on a $v_3$ ou
  $v_4$ qui est vrai et $l=\top$ rend la formule satisfiable.
\end{solution}

\begin{question}
Montrer que $3$-SAT est $\NP$-complet. Pour cela, partir du problème
CNF-SAT (qui est supposé $\NP$-complet) et montrer que pour toute
formule CNF $\varphi$ on peut trouver une formule $\varphi'$ qui est
satisfiable si et seulement si $\varphi$ l'est avec $|\varphi'|$ de
taille polynomiale en $|\varphi|$ et où chaque clause de $\varphi'$
contient au plus $3$ littéraux.
\end{question}

\begin{solution}
Étant donnée une formule CNF, si on a une clause $v_1 \lor \dots \lor
v_k$ avec $k>3$ alors on la transforme $v_1\lor v_2\lor l$ et $\lnot
l\lor v_3 \dots v_k$ qui sont deux formules plus petites. En répétant
ce processus, on obtient une formule CNF équivalente mais dont toutes
les clauses ont au plus 3 littéraux.
\end{solution}

\begin{defi}
  Une formule DNF (pour \emph{Disjunctive Normal Form}) est la donnée
  d'un ensemble de variables $x_1, \dots, x_n$ et d'une disjonction de
  clauses où chaque clause est une conjonction de littéraux. En forme
  logique une formule DNF est donc $\exists x_1, \dots,
  x_n\in\{\bot,\top\}^n:\bigvee_j (\bigwedge_i v_i^j)$
\end{defi}

\begin{question}
Le problème DNF-SAT est celui de la satisfiabilité d'une formule
DNF. Le problème DNF-SAT est-il dans $\NP$ ? $\coNP$ ? $\DP$~?
\end{question}

\begin{solution}
Le problème DNF-SAT est dans ces trois classes. En effet, pour
satisfaire une formule DNF, il suffit de satisfaire l'un de ses
clauses donc on traite clause par clause. Et une clause est
satisfiable si et seulement si elle ne comporte pas un littéral et son
contraire.
\end{solution}

\section{Réduction de 3-SAT à 3-coloriage}

\begin{defi}
Étant donné un graphe $G=(V,E)$, $G$ est dit $k$-coloriable si l'on
peut colorier ses nœuds avec $k$ couleurs de telle façon que deux
nœuds reliés n'ont jamais la même couleur. Formellement, la
$k$-coloriabilité de $G$ s'exprime de la façon logique suivante
$\exists (c:V\rightarrow \{1,\dots,k\})~\forall (i,j)\in E~: c(i)\neq
c(j) $.
\end{defi}

\begin{question}
Montrer que pour tout $k$ fixé, le problème du $k$-coloriage est
dans $\NP$.
\end{question}

\begin{solution}
  Ce problème est dans $\NP$ car on prend le graphe et un certificat
  correspond à choisir une couleur pour chaque nœud tandis que le
  vérificateur correspond à vérifier que le coloriage est bon.
\end{solution}

\begin{question}
Montrer que si le problème de la $k+1$-coloriabilité est dans $\DP$ alors
celui de la $k$-coloriabilité l'est aussi.
\end{question}

\begin{solution}
Si l'on sait résoudre la $k+1$-coloriabilité en temps polynomial alors
il suffit d'ajouter un nœud relié à tous les autres et $k+1$-colorier
le graphe obtenu. En retirant le nœud ajouté on obtient une
$k$-coloration du graphe.
\end{solution}

Nous allons maintenant monter que $3$-SAT se réduit à
$3$-coloriage. Pour cela nous allons introduire plusieurs
gadgets.

\paragraph{Gadget de couleurs}

Dans notre graphe, les trois couleurs vont représenter soit vrai
($\top$), faux ($\bot$) ou autre ($G$ pour Ground). Pour encoder ces
couleurs notre premier gadget est d'inclure le graphe de la
figure~\ref{fig:color}. Nous brancherons ensuite souvent des nœuds à
$G$ ou $\bot$ pour interdire ces couleurs, il s'agira toujours de ces
mêmes nœuds $G$ et $\bot$ (le gadget n'est présent qu'une seule fois
même si ses nœuds sont utilisés dans les autres gadgets).

\begin{question}
Trouver un gadget qui impose qu'un nœud soit colorié de la même
couleur que $\top$.
\end{question}

\begin{figure}
\begin{subfigure}[b]{0.3\textwidth}
\begin{center}
\begin{tikzpicture}[shorten >=1pt,node distance=2cm,on grid,auto]
    \node[state] (V)   {$\top$};
    \node[state] (F) [right=of V] {$\bot$};
    \node[state] (G) [below right=1.5cm and 1cm of V] {$G$};
    \path[-]
    (V) edge  (F)
    (F) edge (G)
    (G) edge (V) ;
\end{tikzpicture}
\end{center}
\caption{Gadget de couleur}
\label{fig:color}
\end{subfigure}
\begin{subfigure}[b]{0.3\textwidth}
\begin{center}
\begin{tikzpicture}[shorten >=1pt,node distance=2cm,on grid,auto]
    \node[state] (x)   {$x_i$};
    \node[state] (n) [below=1.50cm of x] {$\lnot x_i$};
    \node[state] (G) [below left=0.75cm and 2cm of x] {$G$};
    \path[-]
    (x) edge  (n)
    (n) edge (G)
    (G) edge (x) ;
\end{tikzpicture}
\end{center}
\caption{Gadget de littéraux}
\label{fig:lit}
\end{subfigure}
\begin{subfigure}[b]{0.3\textwidth}
\begin{center}
\begin{tikzpicture}[shorten >=1pt,node distance=2cm,on grid,auto]
    \node[state] (R)  {$R$};
    \node[state] (G)  [below left=1.5cm and 3cm of R] {$G$};
    \node[state] (a1) [below left=1.cm and 1.cm of R]  {$\widetilde{a}$};
    \node[state] (b1) [right=of a1] {$\widetilde{b}$};
    \node[state] (a) [below=1.5cm of a1]  {$a$};
    \node[state] (b) [right=of a] {$b$};
    \path[-]
    (a) edge  (a1)
    (a1) edge (R)
    (b) edge  (b1)
    (b1) edge (R)
    (a1) edge (b1)
    (G) edge [bend left] (R) 
    (G) edge (a) 
    (G) edge [bend right=60] (b) ;
\end{tikzpicture}
\end{center}
\caption{Gadget OR}
\label{fig:or}
\end{subfigure}
\end{figure}

\paragraph{Gadget littéraux}

Pour chaque variable $x_i$ nous allons créer deux nœuds : $x_i$ et
$\lnot x_i$ que nous allons brancher à $G$ et entre eux selon le
schéma de la figure~\ref{fig:lit}.


\paragraph{Gadget OR}
Supposons que $a$ et $b$ représentent des valeurs booléennes (ce que
l'on force en les branchant à $G$), le gadget OR est celui de la
figure~\ref{fig:or} (le $G$ est celui du premier gadget).

\begin{question}
  Montrer que dans tout coloriage du gadget, la couleur de $R$ est la
  même que celle de $a$ ou la même que celle de $b$. Et montrer que si
  on limite le graphe à ce gadget, alors $R$ peut être colorié par la
  couleur de $a$ ou par celle de $b$.
\end{question}


\begin{solution}
Soit $a$ et $b$ sont de la même couleur et alors $\widetilde{a}$ et
$\widetilde{b}$ doivent être coloriés en les deux couleurs
complémentaires donc $R$ est forcément colorié de cette couleur
commune.

Soit $a$ et $b$ sont coloriés en $\top$ et $\bot$ tandis que $R$ est
forcément colorié en l'une de ces couleurs puisque $R$ est lié à $G$.
\end{solution}
  
\begin{question}
  Trouver un gadget qui réalise le OR entre trois valeurs booléennes
  $a$, $b$, $c$ (représentées par des nœuds coloriés de la même
  couleur que $\top$ ou $\bot$).
\end{question}

\begin{solution}
\begin{center}
\begin{tikzpicture}[shorten >=1pt,scale=0.6, every node/.style={scale=0.6},node distance=1cm,on grid,auto]
    \node[state] (R)  {$R$};
    \node[state] (G)  [below left=2cm and 3cm of R] {$G$};
    \node[state] (a1) [below left=1.cm and 0.5cm of R]  {$\widetilde{a}$};
    \node[state] (bc1) [right=of a1] {$\widetilde{b\lor c}$};
    \node[state] (a) [below=of a1]  {$a$};
    \node[state] (bc) [right=of a] {$b\lor c$};
    \node[state] (c1) [below left=1.cm and 0.5cm of bc]  {$\widetilde{c}$};
    \node[state] (b1) [right=of c1] {$\widetilde{b}$};
    \node[state] (c) [below=of c1]  {$c$};
    \node[state] (b) [right=of c] {$b$};
    \path[-]
    (a) edge  (a1)
    (a1) edge (R)
    (bc) edge  (bc1)
    (bc1) edge (R)
    (a1) edge (bc1)
    (bc) edge (c1)
    (c1) edge (b1)
    (bc) edge (b1)
    (c) edge (c1)
    (b) edge (b1)
    (G) edge (R) 
    (G) edge (a) 
    (G) edge [bend right=45] (bc) 
    (G) edge [bend right=65] (b)
    (G) edge [bend right=20] (c) ;
\end{tikzpicture}
\end{center}

\end{solution}

\paragraph{Preuve finale}
\begin{question}
Trouver un gadget pour vérifier chacune des clauses.
\end{question}

\begin{solution}
Pour chaque clause $v_1\lor v_2\lor v_3$ on utilise le 3-OR avec
$a=v_1$, $b=v_2$, $c=v_3$ puis on relit $R$ à $G$ et $\bot$. Ce gadget
ne peut être colorié que si un des $v_i$ est colorié avec la couleur
de $\top$.
\end{solution}

\begin{question}
Présenter une réduction polynomiale de $3$-SAT au $3$-coloriage.
\end{question}

\begin{solution}
  Nos gadgets littéraux introduisent $2$ nœuds et $3$ arêtes par
  variable tandis que nos gadgets clauses introduisent $7$ nœuds et
  $12$ arêtes. Dans tous les cas la formules est transformé en graphe
  de taille linéaire et a fortiori polynomial.
\end{solution}

\section{Miscellanées}


\begin{question}
Le problème du $2$-coloriage est-il dans $\NP$ ? $\coNP$ ? $\DP$ ?
\end{question}

\begin{solution}
Le $2$-coloriage est dans $\DP$ car l'algorithme glouton suivant
fonctionne.

On répète la procédure suivante sur chaque composante connexe du
graphe. On choisit un nœud au hasard et on le colorie dans la première
couleur et de parcourir récursivement ses voisins. À chaque fois soit
le voisin n'est pas colorié et on le colorie (de la couleur opposée)
récursivement, soit il est colorié et on vérifie sa couleur.

\end{solution}

\begin{question}
Montrer que SAT se réduit à $3$-SAT (c'est à dire la satisfiabilité de
formules booléennes composées de $\lor$, $\land$, $\lnot$ et de
variables).
\end{question}

\begin{solution}
  On traduit récursivement les formules avec $t$ en CNF. Tout d'abord
  on pousse les négations en bas en utilisant les formules de De
  Morgan puis $t(\varphi\land\psi)=t(\varphi)\land t(\psi)$ ; et pour
  $t(\varphi\lor\psi)$ on ajoute $x$ à chaque clause de $t(\varphi)$
  et $\lnot x$ à chaque clause de $t(\psi)$ et la conjonction des deux
  nous donne ce que l'on veut.

  Cette réduction est polynomiale car si on prend l'arbre de la
  formule, le nombre de clauses est le nombre de feuilles tandis que
  le nombre de littéraux dans une clause est le nombre de or
  rencontrés plus un.
\end{solution}

\begin{question}
Dans quelles classes se trouve le problème $2$-SAT ?
\end{question}

\begin{solution}
  $2$-sat est dans $\DP$. On regarde le graphe dont les nœuds sont les
  littéraux possibles et on met une arête entre $v$ et $\lnot w$ s'il
  existe une clause $v\lor w$. La formule est satisfiable si et
  seulement si une variable et sa négation appartiennent à une
  composante fortement connexe de ce graphe.
\end{solution}

\section{Problème de clique}

\begin{defi}
  Le problème de la clique consiste à décider si étant donné un graphe
  $G$ et un entier $k$ que le graphe $G$ contient une $k$-clique (un
  ensemble de $k$ nœuds tous reliés les uns aux autres).
\end{defi}

\begin{question}
  Montrer que le problème de la clique est $\NP$-complet.

  \emph{Suggestion~: trouver une réduction avec 3-SAT. Étant donné
    $\bigvee_j (\bigwedge_i v^j_i)$ on créé un nœud par $v^j_i$ (si un même
    littéral apparaît dans plusieurs clauses, alors il est présent
    plusieurs fois).}
\end{question}

\begin{solution}
Dans le graphe on relit $v^j_i$ à $v^k_l$ s'il ne sont pas dans la
même clause (i.e. $k\neq j$) et s'il l'un n'est pas la négation de
l'autre. Si l'on trouve une $k$-clique alors il y est possible de
satisfaire $k$ clauses (en prenant $k$ comme le nombre de clause on a
la satisfiabilité de la formule 3-CNF).
\end{solution}

\end{document}

