
\documentclass[12pt]{article}

\usepackage[cp1252]{inputenc}   % LaTeX, comprends les accents !
\usepackage[T1]{fontenc}      % caractères français
\usepackage{lmodern}
%\addtolength{\hoffset}{-1cm}
%\addtolength{\textwidth}{2cm}  % pour les marges
%\addtolength{\voffset}{-1cm}
%\addtolength{\textheight}{2cm}        
\usepackage[a4paper]{geometry}
\usepackage[frenchb]{babel}
\usepackage{bm,amsmath,amssymb,amsthm,graphicx,MnSymbol}
\usepackage[ruled,vlined]{algorithm2e}


%Pour les Automates%
\usepackage{pgf}
\usepackage{tikz}
\usetikzlibrary{arrows,automata,decorations.text}
%%%% autres options %%%%

%\pagestyle{headings}         % Pour mettre des entêtes avec les titres des sections en haut de page

%\usepackage{pgf,tikz}         % Dessiner des Graphes :
%\usetikzlibrary{automata}     % ...Automates
%\usetikzlibrary{arrows}       % ...Flèches
%\usetikzlibrary{petri}        %

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\title{Le Problème de Séparation par Automate est NP-Complet}
   
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%% Commandes utiles %%%%

\newcommand\N{\mathbb{N}}
\newcommand\C{\mathbb{C}}
\newcommand{\Cb}{\overline{\C}}
\newcommand{\conj}{\mathbf{C}}
\newcommand\R{\mathbb{R}}
\newcommand{\Rb}{\overline{\R}}
\newcommand\D{\mathbb{D}}
\renewcommand\H{\mathbb{H}}
\newcommand{\Hb}{\overline{\H}}
\renewcommand{\S}{\mathbb{S}}
\renewcommand\D{\Delta}
\newcommand{\n}{\bigskip}
\renewcommand{\Im}{\mathrm{Im}}
\renewcommand{\Re}{\mathrm{Re}}
\newcommand{\Hom}{\mathrm{Hom}}
\newcommand{\Mob}{\mathrm{Mob}}
\newcommand{\scal}{<\ ,\ >}
\newcommand{\dd}{\mathrm{d}}
\renewcommand{\frac}{\frac}
%\DeclareMathOperator{\D}{\mathcal{D}}


%%%% Commande \subsubsubsection{} %%%%%%
\setcounter{secnumdepth}{4}
\setcounter{tocdepth}{3}
\makeatletter
\newcounter {subsubsubsection}[subsubsection]
\renewcommand\thesubsubsubsection{\thesubsubsection .\@alph\c@subsubsubsection}
\newcommand\subsubsubsection{\@startsection{subsubsubsection}{4}{\z@}%
                                     {-3.25ex\@plus -1ex \@minus -.2ex}%
                                     {1.5ex \@plus .2ex}%
                                     {\normalfont\normalsize\bfseries}}
\newcommand*\l@subsubsubsection{\@dottedtocline{3}{10.0em}{4.1em}}
\newcommand*{\subsubsubsectionmark}[1]{}
\makeatother
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%







\usepackage{thmbox}

\theoremstyle{plain}
\newtheorem{thm}{Théorème}
\newtheorem{lem}{Lemme}
\newtheorem{cor}{Corollaire}


\theoremstyle{definition}

\newtheorem{defi}{Définition}
\newtheorem{prop}{Propriété}
\newtheorem{nota}{Notation}

\theoremstyle{remark}
\newtheorem{exe}{Exemple}
\newcommand{\rem}{\bigskip\emph{Remarque : }}
\newcommand{\dem}{\bigskip\emph{Démonstration : }}

\begin{document}
\maketitle

\begin{thm}
	\emph{Instance :} $k\in\N, S,T\subset\Sigma^*$ des langages finis
	
	\n\emph{Problème PSA:} $\exists ? \mathcal{A}$ un AFD à $k$ états tels que $S\subset\mathcal{L}(\mathcal{A})$ et $T\cap\mathcal{L}({A})=\emptyset$
	
	\n\emph{Théorème :} PSA est un problème NP-complet. 
\end{thm}

\n \emph{Démonstation :} 
\begin{itemize}
	\item \emph{PSA est NP :} On sais créer en temps polynomial un automate à $k$ état et vérifier s'il sépare $S$ et $T$.
	
	\item \emph{PSA est NP-difficile :} On va réduire le problème SAT au problème PSA. Comme SAT est NP-Complet, par le \emph{théorème de Cook}, PSA sera aussi NP-Complet.
\end{itemize}

\n Construisons donc la réduction de SAT à PSA :

Soit $F$ une formule : $$F = \bigwedge_{i=1}^{n-1} C_i, \quad\mathrm{avec}\ x_0,\dots,x_{v-1}\ \mathrm{les\ variables\ de\ } F.$$
On désigne $ x_0,\dots,x_{v-1}, \neg x_0,\dots,\neg x_{v-1}$ par $l_0,\dots,l_{2v-1}$.
On va construire $(k(F),S(F),T(F))$ une instance de PSA tel que si $\exists \mathcal{A}$ à $k$ états qui sépare $S$ et $T$ alors il existe une valuation $\delta$ de $F$ tel que $\delta(F)=1$.

\n Soit $k=n+2v$, on va construire $S(F)$ et $T(F)$ sous forme d'union de sous-langages $S_i$ et $T_i$.

\n \emph{L'objectif de toute la construction des $S_i$ et $T_i$ prennent en compte les propriétés que vérifient les différents objets du problème $SAT(F)$ et de donner l'automate les séparants lorsqu'il peut se construire. On construit alors $\mathcal{A}$ petit à petit.}

\n
\begin{enumerate}
	\item Posons $S_1=\{\epsilon, a^k\}$ et $T=\{ a^i | 0<i<k\}$. On construit l'automate $\mathcal{A}_1$ qui sépare $S_1$ et $T_1$ en nommant les sommets comme suit : $C_0,\dots,C_{n-1},x_0,\dots,x_{v-1},\neg x_0,\dots,\neg x_{v-1}$ :
	
	\begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=2.8cm,
                    semithick]
  \tikzstyle{every state}=[fill=white,draw=black,text=black]

  \node[state] (A)                    {$C_0$};
  \node[state]         (B) [right of=A] 			{$C_1$};
  \node[state]         (C) [right of=B] 			{$C_{n-1}$};
  \node[state]         (D) [right of=C] 			{$x_0$};
  \node[state]         (E) [below right of=D]       {$x_1$};
  \node[state]				 (F) [below left of=E]				{$x_{v-1}$};
  \node[state]				 (G) [left of=F]				{$\neg x_0$};
  \node[state]				 (H) [left of=G]				{$\neg x_1$};
  \node[state]				 (I) [left of=H]				{$\neg x_{v-1}$};
  
  \tikzstyle{every state}=[fill=none, draw=none, text=black]
  
  \node[state]        (Final) [above right of=A]  {};
	\node[state]				(Initial) [left of =A] {};
	
	
  \path (A) edge              node {a} (B)
  					edge							node {} (Final)
        (B) edge [loosely dotted] node {a} (C)
        (C) edge							node {a} (D)
        (D) edge              node {a} (E)
        (E) edge [loosely dotted] node {a} (F)
        (F) edge              node {a} (G)
        (G) edge							node {a} (H)
        (H) edge [loosely dotted] node {a} (I)
        (I) edge              node {a} (A)
        (Initial) edge        node {} (A);
\end{tikzpicture}
	
	
	
		
	\item On veut maintenant que dans $\mathcal{A}_2$, on ait $C_j\stackrel{b}{\rightarrow} l_i$ lorsque $l_i$ est une variable de $C_j$. C'est à dire que $\mathcal{A}_2$ est tel que $S_1\subset\mathcal{A}_2$ et $(T_1\cup T_2)\cap\mathcal{A}_2=\emptyset$ avec $T_2=\{a^iba^j | 0\geq i < n et 0\geq j <k\}\setminus\{a^iba^{2v-j} | l_j\ \mathrm{terme\ de\ } C_i\}$.
	
	\item On veut ensuite que $\forall i\in[|0,2v-1|], l_i \stackrel{b}{\rightarrow} C_0$ ou $l_i \stackrel{b}{\rightarrow} \neg x_0$. $C_0$ et $x_0$ sont désormais vu comme VRAI et FAUX respectivement.
	C'est à dire que $\mathcal{A}_3$ sépare $S_1$ et $(T_1\cup T_2 \cup T_3)$ où $T_3=\{a^{n+j}ba^h | j\in[|0,2v-1|], 0<h<k\ \mathrm{et}\ h\neq v\}$.
	
	\item On veut que les variables $x_i$ et $\neg x_i$ ne soient jamais vraies en même temps, c'est à dire qu'il n'y a pas de succession de transitions dans $\mathcal{A}_4$  de la forme :
	$$C_0\stackrel{a^{n+j}}{\rightarrow} x_j \stackrel{b}{\rightarrow} C_0 \stackrel{a^{n+v+j}}{\rightarrow} \neg x_j \stackrel{b}{\rightarrow} C_0,\quad \forall j\in[|0,v-1|]$$
	C'est à dire que $\mathcal{A}_4$ sépare $S_1$ et $(T_1\cup T_2\cup T_3\cup T_4)$ où $T_4=\{a^{n+j}ba^{n+v+j}b | \forall j\in[|0,v-1|]\}$
	
	\item Enfin, on veut que si $C_i \stackrel{b}{\rightarrow} l_j$ alors $l_j\stackrel{b}{\rightarrow} VRAI/ (=C_0)$. C'est à dire que $\mathcal{A}_5$ sépare $(S_1\cup S_2)$ et $(T_1\cup\dots\cup T_4)$ où $S_2=\{a^ibb | \forall i \in[|0,n-1|]\}$.
\end{enumerate}

\n On a ainsi une application $F\mapsto(k(F),S(F), T(F))$ calculable en temps polynomial car $S$ et $T$ sont en $O(n+v)$. Il reste a bien vérifier que c'est bien une réduction de SAT à PSA.

\n Si l'automate $\mathcal{A}$ à $k$ états peut bel et bien être construit comme plus haut, il sépare $S$ et $T$ et alors on pose la valuation $\delta : \forall i\in[|1,v-1|], \delta(x_i)=1$ si $x_i\stackrel{b}{\rightarrow} C_0$, $0$ sinon.
Alors $\forall j$, la clause $C_j$ est reliée à un littéral $l_i$ tel que $l_i\stackrel{b}{\rightarrow} C_0$. Si $l_i$ est une variable $x$, $\delta(x)=1$ implique que $C_j$ est satisfaite, si $l_i$ est une variable $\neg x$, alors $\delta(\neg x)=1-\delta(x)=1$ et implique encore que $C_j$ est satisfaite. Donc $\delta(F)=1$.

\n \emph{Remarque :}
 Réciproquement, si $F\in SAT$, soit $\phi$ valuation telle que $\phi(F)=1$. On note $t(C_i)$ le premier littéral de la classe $C_i$ tel que $\phi(t(C_1))=1$. 
On construit alors l'automate déterministe $\mathcal{A}=(Q,\Sigma,\delta,C_0,{C_0})$ avec $Q=\{C_0,\dots,C_{n-1},x_0,\dots,x_{v-1},\neg x_0,\dots,\neg x_{v-1}\}$ et $\delta$ définie de la manière suivante :
$$\begin{array}{cccc}
			\delta(q_i,a)&=&q_{i+1 \mathrm{mod} k} \quad \forall 0\geq i < k \\
			\delta(C_i,b)&=&t(C_i)   \quad \forall i\in[|0,n-1|] \\
			\delta(l_i,b)&=&\delta(l_i)=C_0\ \mathrm{si}\ \delta(l_i)=1\ \mathrm{pour}\ 0\geq 1<2v, \quad \neg x_0\ \mathrm{sinon}  \end{array}$$
			
On a alors $S_F\subset \mathcal{L}(\mathcal{A})$ et $T_F\cap \mathcal{L}(\mathcal{A})=\emptyset$.


\end{document}