\chapter{\textsf{Gen}, un Problème Algébrique} \begin{defn}\label{def-closure} Soit $X$ un ensemble, $\bullet$ une opération binaire sur $X$, et $R \subseteq X$, alors $\closure{R}{\bullet}$ est la \defin{clôture} de $R$ pour l'opération $\bullet$, qu'on définit par sa construction: \begin{algorithmic}[1] \State $\lstTwo{R'}{\closure{R}{\bullet}} \gets S$ \While{$R' \neq \emptyset$} \State $R' \gets \setcond{k \notin \closure{R}{\bullet}}{\exists \lstTwo{i}{j} \in \closure{R}{\bullet} \text{ et } i \bullet j = k}$ \State $\closure{R}{\bullet} \gets \closure{R}{\bullet} \cup R'$ \EndWhile \end{algorithmic} \end{defn} \begin{defn}\cite{JL76} $\GenR$\\ Donnée: Un ensemble $X$, une opération binaire $\bullet$ sur $X$ (donné sous forme d'un tableau de taille $\cardnSym{X}^2$), un sous-ensemble $R \subseteq X$ et un élément $x \in X$.\\ Question: Est-ce que $x \in \closure{R}{\bullet}$? \end{defn} \begin{prop}\cite{JL76} $\GenR $ est $\Complete{\PClass}$ selon $\reducLog$. \end{prop} \begin{defn}\cite{BM91} $\Gen$\\ Donnée: Un tableau $n \times n$ qui décrit une opération binaire $\bullet$ sur $\range{n}$.\\ Question: Est-ce que $n \in \closure{\setOne{1}}{\bullet}$? \end{defn} \begin{prop}\cite{BM91}\cite{JL76} $\Gen$ est $\Complete{\PClass}$ selon $\reducLog$. \end{prop} \begin{defn}\label{def-temoinGEN} Soit $\bullet$ une opération binaire sur $\range{n}$, $R$ un sous-ensemble non-vide de $\range{n}$ et $x \in \closure{R}{\bullet}$, alors un \defin{témoin} de $x \in \closure{R}{\bullet}$ est une arborescence binaire entière $\tuplThree{S}{A}{s_0}$ munie d'un étiquetage $\lambda: S \to \range{n}$ tel que \begin{itemize} \item $\fofOne{\lambda}{s_0} = x$ \item Si $s$ est interne, alors $\fofOne{\lambda}{\text{enfant gauche de } s} \bullet \fofOne{\lambda}{\text{enfant droit de } s} = \fofOne{\lambda}{s} \notin R$ \item Si $s$ est feuille, alors $\fofOne{\lambda}{s} \in R$. \end{itemize} Deux témoins $T_1$ et $T_2$ pour un même $\bullet$, $R$ et $x$ sont \textit{distincts} (i.e. $T_1 \neq T_2$) si leurs graphes sous-jacents ne sont pas isomorphes, ou bien si l'isomorphisme existant lie deux sommets qui n'ont pas la même étiquette. Il est évident que $x \in \closure{R}{\bullet} \iff \exists$ un témoin de $x \in \closure{R}{\bullet}$. \end{defn} \section{Saut de \textsf{NL} à \textsf{P} entre \textsf{Gen}-1 et \textsf{Gen}-2} \begin{defn}$\GenT{t}$\\ Même problème que $\Gen$ avec une restriction sur la donnée: $\forall k \in \range{n} \setminus \setOne{1}$, $k$ est présent au plus $t$ fois dans le tableau (i.e. il existe au plus $t$ couple(s) $\tuplTwo{i}{j}$ tel(s) que $i \bullet j = k$). \end{defn} \begin{lem}\label{prop-GENTreeHeight} Soit $\bullet$ une opération binaire sur $\range{n}$, $R$ un sous-ensemble non-vide de $\range{n}$ et $x \in \closure{R}{\bullet}$, alors $\exists T$ témoin de $x \in \closure{R}{\bullet}$ d'une hauteur $\fofOne{h}{T} \leq n$. \end{lem} \begin{proof} Soit $T$ le témoin de $x \in \closure{R}{\bullet}$, promis par $x \in \closure{R}{\bullet}$, qu'on suppose tel que $\fofOne{h}{T} > n$. Ainsi, il existe au moins une chaîne entre la racine $s_0$ et une feuille telle que $s \neq s'$ dans la chaîne ont une étiquette $\fofOne{\lambda}{s} = \fofOne{\lambda}{s'}$. On suppose sans perte de généralité que $s$ est un ancêtre de $s'$, puis on remplace la sous-arborescence de racine $s$ par celle de racine $s'$ afin d'obtenir un nouveau témoin de $x \in \closure{R}{\bullet}$ qui a une répétition d'étiquette en moins. Ce processus est répété jusqu'à ce qu'aucune telle chaîne ait une répétition d'étiquette, ce qui résulte en un témoin d'hauteur au plus $n$. \end{proof} \begin{lem}\label{prop-GEN1UniqueTree} Soit $\bullet$ sur $\range{n}$ tel que $\forall k \in \range{n} \setminus \setOne{1}$ il existe au plus un couple $\tuplTwo{i}{j} : i \bullet j = k$ et $R$ un sous-ensemble non-vide de $\range{n}$. Alors, $\forall x \in \closure{R}{\bullet}$, il existe un témoin unique de $x \in \closure{R}{\bullet}$. \end{lem} \begin{proof} On montre par induction que $\Pred{m}$ est vrai $\forall m \geq 0$, où $\Pred{m}$ est vérifié si $\forall \lstTwo{T_1}{T_2}$ deux témoins de $x \in \closure{R}{\bullet}$ tels que $m = \max\setTwo{\fofOne{h}{T_1}}{\fofOne{h}{T_2}}$, on a $T_1 = T_2$. Soient $T_1$ et $T_2$ deux témoins de $x \in \closure{R}{\bullet}$ tels que $\max\setTwo{\fofOne{h}{T_1}}{\fofOne{h}{T_2}} = 0$. On a que $\fofOne{h}{T_1} = \fofOne{h}{T_2} = 0$ et donc, par \ref{def-temoinGEN}, $T_1$ et $T_2$ doivent chacun être une arborescence composée d'une seule feuille racine avec étiquette $\fofOne{\lambda}{s_0} = x$. Ainsi, $T_1 = T_2$, ce qui prouve $\Pred{0}$. Avec l'hypothèse d'induction $\forall l \leq m, \Pred{l}$, on suppose par contradiction $\exists T_1 \neq T_2$ deux témoins de $x \in \closure{R}{\bullet}$ de hauteur au plus $m + 1$. Étant donné que $i \bullet j$ est l'unique produit possible qui donne $x$, on a que l'étiquette de l'enfant gauche des racines de $T_1$ et $T_2$ est $i$. On suppose sans perte de généralité que la sous-arborescence $G_1$ de $T_1$ avec racine étiquetée $i$ diffère de la sous-arborescence $G_2$ de $T_2$ avec racine étiquetée $i$. Pourtant, avec l'hypothèse d'induction on doit avoir $G_1 = G_2$, parce que $\lstTwo{\fofOne{h}{G_1}}{\fofOne{h}{G_2}} \leq m$. Cette contradiction indique que $\Pred{m + 1}$ doit être vrai et donc $\Pred{m}$ est vrai $\forall m \geq 0$. \end{proof} \newcommand{\src}{s_{\mathrm{src}}} \newcommand{\dest}{s_{\mathrm{dest}}} \begin{defn}\cite{J75} $\STCONN$\\ Donnée: Un graphe orienté $G = \tuplTwo{S}{A}$ donné par sa matrice d'adjacence, un sommet source $\src$ et un sommet destination $\dest$\\ Question: Est-ce qu'il existe un chemin de $\src$ à $\dest$ dans $G$? \end{defn} \begin{defn}$\STCONNlt$\\ Même problème que $\STCONN$ avec quelques restrictions sur la donnée: \begin{enumerate}[label=\textbf{\arabic*.}] \item $G$ ne contient aucun circuit \item $\outdeg{\dest} = 0$ \item $\forall s \in S, \outdeg{s} \leq 2$ \item $\forall i \neq j \in S, \exists$ au plus un sommet $s \in S$ tel que $\lstTwo{\tuplTwo{s}{i}}{\tuplTwo{s}{j}} \in A$ \end{enumerate} \end{defn} \begin{lem} $\STCONNlt \in \Hard{\NLClass}$. \end{lem} \begin{proof} Par \cite{J75} on a que $\STCONN \in \Hard{\NLClass}$ selon $\reducLog$. Par transitivité de $\reducLog$, il suffit de montrer que $\STCONN \reducLog \STCONNlt$ afin d'avoir $\STCONNlt \in \Hard{\NLClass}$. Plutôt que construire une seule \gls{mT}, on en construit trois qui, une à la suite de l'autre, réduisent $\STCONN$ à $\STCONNlt$. Si, en plus, chacune des \gls{mT} utilise un espace logarithmique, on conclut que $\STCONN \reducLog \STCONNlt$ par la transitivité de $\reducLog$. La première \gls{mT} $M_1$ va simplement, pour chaque sommet $s \in S : \outdeg{s} > 2$, ajouter de nouveaux sommets afin de créer une arborescence binaire dont la racine est $s$ et les feuilles sont les sommets $t \in S : \tuplTwo{s}{t} \in A$. On a aussi que la taille de chaque arborescence construite est polynomiale, ainsi, $M_1$ réutilise son espace logarithmique pour compter les sommets ajoutés, pour chaque $s \in S : \outdeg{s} > 2$. La seconde \gls{mT} $M_2$ construit un graphe $G' = \tuplTwo{S'}{A'}$ qui satisfait la condition \textbf{1} à partir de $G$ en entrée. On applique la technique de \textit{timestamp} utilisée dans \cite[Corollaire~25]{J75}, donc $M_1$ copie les sommets du graphe $G$ initial $\cardnSym{S}$ fois, puis ajoute un arc d'un sommet d'une copie au sommet de la suivante s'il y avait un tel arc dans $G$. Formellement, $S' = \setcond{\tuplTwo{i}{s}}{1 \leq i \leq \cardnSym{S} \text{ et } s \in S}$ et $A' = \setcond{\tuplTwo{\tuplTwo{i}{s}}{\tuplTwo{i + 1}{t}}}{\tuplTwo{s}{t} \in A}$. Afin d'avoir $\src' = \tuplTwo{1}{\src}$ et $\dest' = \tuplTwo{n}{\dest}$, on doit aussi ajouter les arcs $\setcond{\tuplTwo{\tuplTwo{i}{\dest}}{\tuplTwo{i + 1}{\dest}}}{1 \leq i < \cardnSym{S}}$. Clairement, aucun circuit n'est possible dans $G'$ car un arc existe seulement d'une copie à la suivante, ce qui satisfait la condition \textbf{1}. Le graphe $G'$ construit satisfait aussi la conditon \textbf{2}, car $\outdeg{\dest'} = 0$. On a aussi que $M_1$ fonctionne en espace logarithmique tel que promis par \cite[Corollaire~25]{J75}. Le calcul de la dernière \gls{mT} $M_3$ concerne chaque sommet $s \in S' : \outdeg{s} = 2$. On pose donc $\lstTwo{i}{j} \in S' : \lstTwo{\tuplTwo{s}{i}}{\tuplTwo{s}{j}} \in A'$. $M_3$ va créer de nouveaux sommets $i'$ et $j'$, puis remplacer les arcs $\tuplTwo{s}{i}$ et $\tuplTwo{s}{j}$ par de nouveaux arcs $\tuplTwo{s}{i'}$, $\tuplTwo{s}{j'}$, $\tuplTwo{i'}{i}$ et $\tuplTwo{j'}{j}$ dans $A'$. Ainsi, $s$ n'est plus candidat avec un arc vers $i$ et $j$ à la fois et il n'y a que $s$ avec un arc vers $i'$ et $j'$. On a que $M_3$ utilise évidemment un espace logarithmique. Chaque \gls{mT} préserve l'existence d'un chemin de $\src$ à $\dest$ dans $G$. En effet, $M_1$ et $M_3$ remplacent possiblement une arcs par plusieurs et pour $M_2$, si un chemin existe de longueur $l$ existe de $s$ à $t$ dans $G$ alors un chemin existe de $\tuplTwo{1}{s}$ à $\tuplTwo{l}{t}$ dans $G'$. \end{proof} \begin{defn}$\STCONNeq$\\ Même problème que $\STCONN$ avec quelques restrictions sur la donnée: \begin{enumerate}[label=\textbf{\arabic*.}] \item $G = \tuplTwo{\range{n}}{A}$ ne contient aucun circuit \item $\forall s \in \range{m + 1}, \outdeg{s} = 0$ \item $\forall s \in \range{n} \setminus \range{m + 1}, \outdeg{s} = 2$ \item $\forall i \neq j \in \range{n}, \exists$ au plus un sommet $s \in \range{n}$ tel que $\lstTwo{\tuplTwo{s}{i}}{\tuplTwo{s}{j}} \in A$ \end{enumerate} Avec $1 \leq m < n - 1$ \end{defn} \begin{lem} $\STCONNeq \in \Hard{\NLClass}$. \end{lem} \begin{proof} Comme pour la preuve précédente, il suffit de montrer que $\STCONNlt \reducLog \STCONNeq$ afin d'avoir $\STCONNeq \in \Hard{\NLClass}$. On construit deux \gls{mT} qui réduisent $\STCONNlt$ à $\STCONNeq$. Si, en plus, chacune des \gls{mT} utilise un espace logarithmique, on conclut que $\STCONNlt \reducLog \STCONNeq$ par la transitivité de $\reducLog$. La première \gls{mT} $M_1$ s'assure simplement que $\forall s \in S, \outdeg{s} = 0$ ou $2$. Pour chaque sommet $s \in S : \outdeg{s} = 1$, $M_1$ ajoute un nouveau sommet $t$ et un arc $\tuplTwo{s}{t}$. Un cas spécial est le sommet $\src$, pour garantir $\outdeg{\src} = 2$, on lui ajoute jusqu'à deux arcs vers de nouveaux sommets. Chaque ajout se fait en espace $\bigO{\fofOne{\log}{n}}$, en bouclant sur les $n^{\bigO{1}}$ sommets $M_1$ réutilise donc son espace logarithmique. La seconde \gls{mT} $M_2$ construit un graphe $G' = \tuplTwo{S'}{A'}$ à partir de $G$ en entrée. On pose $n = \cardnSym{S}$, $S' = \range{n}$ et $m + 1 = \cardnSet{\setcond{s \in S}{\outdeg{s} = 0}}$. Le renommage des sommets s'effectue à l'aide d'une bijection $f: S \to \range{n}$ où $\forall s \in S$ tel que \resp{$\outdeg{s} = 0$}{$\outdeg{s} = 0$}, $\fofOne{f}{s} = i$ tel que $s$ est le $i$-ème sommet avec \resp{$\outdeg{s} = 0$}{$\outdeg{s} = 0$}. Compter les sommets et calculer le demi-degré extérieur se fait en espace $\bigO{\fofOne{\log}{n}}$ pour chaque sommet, en bouclant sur les $n^{\bigO{1}}$ sommets et arcs $M_2$ réutilise donc son espace logarithmique. On note que $\outdeg{\src} = 2$ et la condition \textbf{1} de $\STCONNlt$ nous assure que $1 \leq m < n - 1$. Chaque \gls{mT} préserve l'existence d'un chemin de $\src$ à $\dest$ dans $G$, ainsi que les conditions \textbf{1} et \textbf{4} de $\STCONNlt$. \end{proof} \begin{thm} $\GenT{1} \in \Complete{\NLClass}$ selon $\reducLog$. \end{thm} \begin{proof} Par le théorême d'Immerman-Szelepcsényi\cite{I88}\cite{S88}, $\NLClass = \Co{\NLClass}$. Nous obtiendrons $\GenT{1} \in \NLClass$ en démontrant en première partie de preuve du théorème que le complément $\setnot{\GenT{1}}$ de $\GenT{1}$ est dans $\Co{\NLClass}$. On a $w \in \GenT{1}$ si $w$ décrit (sous forme de tableau) l'opération $\bullet$ sur $\range{n}$ telle que $n \in \closure{\setOne{1}}{\bullet}$ et $\forall k \in \range{n} \setminus \setOne{1}$, au plus un couple $\tuplTwo{i}{j}$ donne $i \bullet j = k$. La machine de Turing non-déterministe $N$ que l'on construit pour décider $\setnot{\GenT{1}}$ doit donc accepter dès qu'une des deux conditions n'est pas respectée. \newcommand{\ParcoursTemoin}[2]{\fofTwo{\textsc{ParcoursTémoin}}{#1}{#2}} Pour déterminer si la condition d'unicité n'est pas respectée, $N$ boucle sur $k \in \range{n} \setminus \setOne{1}$. Pour chaque $k$, $N$ parcourt le tableau $x$ et accepte si $k$ est présent plus d'une fois, sinon $N$ continue avec l'exécution de $\ParcoursTemoin{n}{n}$ selon l'algorithme non-déterministe suivant: \begin{algorithmic}[1] \Procedure{ParcoursTémoin}{$\lstTwo{h}{k}$} \If{$k = 1$} \State $N$ refuse \ElsIf{$h = 0$ ou $\nexists \tuplTwo{i}{j}$ tel que $i \bullet j = k$} \State $N$ accepte \EndIf \State $\tuplTwo{i}{j} \gets$ l'unique couple $\tuplTwo{i}{j}$ tel que $i \bullet j = k$ \State Choix non-déterministe entre $\ParcoursTemoin{h - 1}{i}$ et $\ParcoursTemoin{h - 1}{j}$ \EndProcedure \end{algorithmic} La recherche d'un couple $\tuplTwo{i}{j}$ dans le tableau $\GenT{1}$, ainsi que mémoriser les variables $\lstTwo{h}{k} \in \range{n}$, se fait en espace logarithmique, qui est réutilisé pour chaque exécution de la procédure. % % CUT FROM HERE % $\Pred{h}$ est vérifié si $\clause{\forall k \in \range{n}}, \exists$ témoin de $k \in \closure{\setOne{1}}{\bullet}$ avec hauteur $\leq h \iff$ tous les chemins de $\ParcoursTemoin{h}{k}$ mènent au rejet. Pour $\Pred{0}$, on observe que $\clause{\forall k \in \range{n}}, \ParcoursTemoin{h}{k}$ refuse \ssi{} $k = 1$, et que le seul témoin avec hauteur $0$ est celui de $1 \in \closure{\setOne{1}}{\bullet}$. Pour $\Pred{h + 1}$, on suppose $\exists$ témoin de $k \in \closure{\setOne{1}}{\bullet}$ avec hauteur $\leq h + 1$. Ainsi, on doit avoir l'existence de témoins de $i \in \closure{\setOne{1}}{\bullet}$ et $i \in \closure{\setOne{1}}{\bullet}$ (tels que $i \bullet j = k$) avec hauteurs $\leq h$. On sait donc que $\ParcoursTemoin{h + 1}{k}$ mène au rejet si $k = 1$ ou bien, par hypothèse d'induction, à la dernière ligne en choisissant $\ParcoursTemoin{h}{i}$ ou $\ParcoursTemoin{h}{j}$. Inversement, on suppose $\nexists$ témoin de $k \in \closure{\setOne{1}}{\bullet}$ avec hauteur $\leq h + 1$. On ne peut avoir $k = 1$, mais s'il n'y a pas de $\lstTwo{i}{j}$ tels que $i \bullet j = k$, alors $N$ accepte. Pour la suite, on suppose sans perte de généralité que $\nexists$ témoin de $i \in \closure{\setOne{1}}{\bullet}$ avec hauteur $\leq h$. Donc, par hypothèse d'induction, $\ParcoursTemoin{h}{i}$ ne refuse pas sur tous les chemins, de même pour $\ParcoursTemoin{h + 1}{k}$. Par $\Pred{n}$, on a donc que $\exists$ témoin de $n \in \closure{\setOne{1}}{\bullet}$ \ssi{} tous les chemins de $\ParcoursTemoin{n}{n}$ mènent au rejet. Ainsi, $N$ décide $\setnot{\GenT{1}}$ en espace logarithmique. Ceci conclut la preuve que $\GenT{1} \in \NLClass$ Il nous reste à démontrer que $\GenT{1}$ est $\Hard{\NLClass}$ selon $\reducLog$. Parce que $\NLClass = \Co{\NLClass}$, un langage est $\Hard{\NLClass}$ selon $\reducLog$ \ssi{} son complément l'est aussi. Il suffit donc de montrer que $\STCONNeq \reducLog \setnot{\GenT{1}}$. Soit un exemplaire de $\STCONNeq$ donné par $G = \tuplTwo{\range{n}}{A}$ et $m$. La réduction consiste à définir sur $\range{n}$ le produit \[ i \bullet j = \begin{cases} k & \text{si } i < j \text{ et } \lstTwo{\tuplTwo{k}{i}}{\tuplTwo{k}{j}} \in A\\ j + 1 & \text{si } i = j < m\\ 1 & \text{sinon } \end{cases} \] Le produit est bien défini sur tout $\range{n}$ et chaque paire $\lstTwo{i}{j}$ donne un unique résultat. En effet, les deux premières lignes ont des conditions mutuellement exclusives et chacune offre un seul résultat possible; la première par la condition \textbf{4} de $\STCONNeq$ qui assure l'unicité d'un tel $k$, la seconde par évidence. Aussi, ce produit respecte la condition d'unicité de $\GenT{1}$. C'est-à-dire qu'il n'y a pas de collision parmi les $k$ et $j + 1$ ou entre les deux. En effet, par la condition \textbf{3} de $\STCONNeq$, $k$ est le résultat d'un seul produit $i \bullet j$ et seulement lorsque $i < j$ (donc, $j \bullet i \neq k$) et on ne peut avoir $k = j + 1$, car $\outdeg{k} = 2$ donc $k > m + 1$ par la condition \textbf{2} de $\STCONNeq$, mais $j + 1 < m + 1$. Le calcul du tableau qui décrit le produit $\bullet$ s'effectue en espace logarithmique, car, pour chaque paire $\lstTwo{i}{j}$, on réutilise l'espace nécessaire pour chercher dans $A$, ce qui se fait en espace logarithmique. On note les propriétés suivantes du produit construit, que l'on utilisera par la suite \begin{enumerate}[label=\alph*.] \item $\closure{\range{m}}{\bullet} = \closure{\setOne{1}}{\bullet}$ \item $\forall k \in \range{n}, k \in \closure{\range{m + 1}}{\bullet}$ \item $\forall p \in \range{m + 1}$, un puits du graphe $G$, et $\forall k \in \range{n}$, un chemin de $k$ à $p$ existe dans $G$ \ssi{} l'unique témoin de $p \in \closure{\range{m + 1}}{\bullet}$ possède une feuille avec étiquette $p$ \end{enumerate} Parce que $\forall 1 \leq j < m, j \bullet j = j + 1$, on a que $\range{m} \subseteq \closure{\setOne{1}}{\bullet}$. Ainsi, avec $\closure{\setOne{1}}{\bullet} \subseteq \closure{\range{m}}{\bullet}$ qui est évident, on a que la propriété \textbf{a} est vérifiée. Avant de prouver \textbf{b}, on introduit $\fofOne{L}{k}$ la longueur d'un des plus long(s) chemin(s) de $k \in \range{n}$ à un des puits $p \in \range{m + 1}$ dans $G$. On note que $\fofOne{L}{k}$ est bien défini parce que $G$ ne contient aucun circuit, ainsi la longeur des plus long(s) chemin(s) entre chaque pair de sommets est finie. Aussi, un chemin existe toujours de $k$ à un des puits $p \in \range{m + 1}$ dans $G$ car les puits sont les seuls sommets avec demi-degré extérieur nul. Pour prouver \textbf{b}, on procède par induction sur $l$ avec le prédicat $\Pred{l}$ qui est vérifié si $\forall k \in \range{n} : \fofOne{L}{k} = l, k \in \closure{\range{m + 1}}{\bullet}$. On a $\Pred{0}$, car $k \in \range{m + 1}$. Ensuite, avec $k \in \range{n}: \fofOne{L}{k} = l + 1$, on pose $\lstTwo{\tuplTwo{k}{i}}{\tuplTwo{k}{j}} \in A$. Évidemment, on a $\lstTwo{\fofOne{L}{i}}{\fofOne{L}{j}} < \fofOne{L}{k} = l + 1$ et donc, avec l'hypothèse d'induction, $\lstTwo{i}{j} \in \closure{\range{m + 1}}{\bullet}$. Ainsi, $i \bullet j = k \in \closure{\range{m + 1}}{\bullet}$ et la propriété \textbf{b} est vérifiée. On démontre la propriété \textbf{c}. Soient d'abord un puits $p \in \range{m + 1}$ et un sommet $k \in \range{n}$ tels qu'un chemin de $k$ à $p$ existe dans $G$. Si un tel chemin est de longueur $0$, alors $k = p$ et le témoin de $k \in \closure{\range{m + 1}}{\bullet}$ est une feuille étiquetée $p$. Sinon la distance de $k$ à $p$ dans $G$ est réalisée par un chemin de longueur $l > 0$ sur les sommets $\lstFive{k}{i_1}{\dots}{i_{l - 1}}{p}$. L'unique témoin de $k \in \closure{\range{m + 1}}{\bullet}$ a donc une racine étiquetée $k$ et un enfant dont l'étiquette est un facteur de l'unique produit qui donne $k$, c'est-à-dire $i_1$. Puisque la distance de $i_1$ à $p$ dans $G$ est $l - 1$, par l'hypothèse d'induction, l'unique témoin de $i_1 \in \closure{\range{m + 1}}{\bullet}$ possède une feuille avec étiquette $p$. Il en va de même pour le témoin de $k \in \closure{\range{m + 1}}{\bullet}$. Inversement, supposons que l'unique témoin $T$ de $k \in \closure{\range{m + 1}}{\bullet}$ possède une feuille étiquetée $p \in \range{m + 1}$. Si la hauteur de $T$ est $0$, alors $k = p$ et donc un chemin de longueur nul existe de $k$ à $p$ dans $G$. Sinon, la racine étiquetée $k$ de $T$ possède deux enfants étiquetés $i$ et $j$ tels que $i \bullet j = k$ et donc $\lstTwo{\tuplTwo{k}{i}}{\tuplTwo{k}{j}} \in A$. Supposons, sans perte de généralité, qu'une feuille promise avec étiquette $p$ du témoin $T$ provient de la sous-arborescence $T_i$ de $T$ enraciné au sommet étiqueté $i$. $T_i$ est donc l'unique témoin de $i \in \closure{\range{m + 1}}{\bullet}$ et possède une feuille étiquetée $p$. Puisque la hauteur de $T_i$ est strictement moins que celle de $T$, par induction, il existe un chemin de $i$ à $p$ dans $G$. Puisque l'arc $\tuplTwo{k}{i} \in A$, alors un chemin de $k$ à $p$ existe aussi dans $G$. Maintenant que les propriétés \textbf{a}, \textbf{b} et \textbf{c} sont vérifiées, nous pouvons confirmer que la construction réduit correctement $\STCONNeq$ à $\setnot{\GenT{1}}$. Supposons qu'un chemin de $n$ à $m + 1$ existe dans $G$. Il ne peut exister un témoin $n \in \closure{\range{m}}{\bullet}$ car ce dernier serait aussi témoin de $n \in \closure{\range{m + 1}}{\bullet}$, sans feuille étiquetée $m + 1$, mais la propriété \textbf{c} nous promet que l'unique témoin a une feuille avec cette étiquette. Ainsi, $n \notin \closure{\range{m}}{\bullet} = \closure{\setOne{1}}{\bullet}$. Inversement, supposons qu'aucun chemin de $n$ à $m + 1$ n'existe dans $G$. L'unique témoin de $n \in \closure{\range{m + 1}}{\bullet}$ ne possède pas de feuille étiquetée $m + 1$, par la propriété \textbf{c}. Ce témoin en est donc un de $n \in \closure{\range{m}}{\bullet} = \closure{\setOne{1}}{\bullet}$. \end{proof} \begin{prop} $\GenT{2}$ est $\Complete{\PClass}$ selon $\reducLog$. \end{prop} \begin{proof} Évidemment $\GenT{2} \in \PClass$, car une instance de $\GenT{2}$ est aussi une instance de $\Gen \in \PClass$. Étant donné que $\Gen$ est $\Hard{\PClass}$, il suffit d'utiliser la transitivité de $\reducLog$ et de montrer que $\Gen \reducLog \GenT{2}$ pour avoir $\GenT{2}$ est $\Hard{\PClass}$. On pose $\Sigma$ et $\Sigma'$ les alphabets de $\Gen$ et $\GenT{2}$ respectivement, et $f : \Sigma^* \to \Sigma'^*$ la réduction qui prend la description d'une opération $\bullet$ sur $\range{n}$ en entrée et écrit la description d'une opération $\circ$ 'équivalente?'. L'idée générale de la réduction est de renommer les entrées dupliquées. Par exemple, si $i_1 \bullet j_1 = i_2 \bullet j_2 = i_3 \bullet j_3 = 2$, alors on introduit plusieurs "$2$" tels que $i_1 \circ j_1 = 2_1$, $i_2 \circ j_2 = 2_2$, $i_3 \circ j_3 = 2_3$. Par contre, il n'est pas possible pour $f$ de déterminer quel produit est nécessaire au calcul de la fermeture de $\setOne{1}$ sous $\bullet$. Donc, en continuant l'exemple, on ajoute les produits qui cascadent vers le "vrai" $2$, $1 \circ 2_1 = 2_2$, $1 \circ 2_2 = 2_3$ et $1 \circ 2_3 = 2'$. Ainsi, peu importe lequel des "$2$" est généré, celui-ci va générer le "vrai" $2$. %On calcule un décalage $d = n^3 + 1$. Le tableau qui décrit l'opération $\circ$ a deux sections importantes: la première est la rangée $1$ avec $n$ régions de chacune $n^2$ cases, la seconde est un carré $n$ par $n$. Chaque région de la première rangée représente un élément de $\range{n}$ On commence par décrire chaque région de la rangée $1$. À l'exception de la dernière case de la région, la $j$-ème case de d'une région contient l'élément $1 \circ j = j + 1$. Pour ce qui est de la dernière case, celle-ci dépend de la région. Dans la $k$-ème région, la dernière case contient l'élément $1 \circ j = n^3 + k$. Ainsi, dès qu'un élément de la région est généré, la dernière case l'est aussi. Dans l'exemple plus haut, le "vrai" $2$ est cette dernière case. La section du carré commence aux coordonnées $\tuplTwo{n^3 + 1}{n^3 + 1}$ et est définie en termes du tableau original qui décrit $\bullet$. L'élément aux coordonnées $\tuplTwo{i}{j}$ du carré (et donc $\tuplTwo{i + n^3 + 1}{j + n^3 + 1}$ du tableau qui décrit l'opération $\circ$) contient un élément qui génère la $\paren{i \bullet j}$-ème région de la rangée $1$. Cet élément doit aussi être unique dans le cas où $i_1 \bullet j_1 = i_2 \bullet j_2$. Pour qu'il soit unique, on décale l'élément de $\paren{i - 1}n + j$. Finalement, on a que l'élément aux coordonnées $\tuplTwo{i}{j}$ du carré est $\paren{\paren{i \bullet j} - 1} n^2 + \paren{i - 1}n + j$. Le tableau construit décrit donc l'opération $i \circ j$ suivante: \[ \begin{cases} n^3 + k & \text{si } i = 1 \text{ et } \exists k \in \range{n} : j = kn^2\\ j + 1 & \text{si } i = 1 \text{ et } j < n^3\\ \paren{\paren{i - n^3 \bullet j - n^3} - 1} n^2 + \paren{i - n^3 - 1} n + \paren{j - n^3} & \text{si } i,j > n^3\\ 1 & \text{sinon} \end{cases} \] On montre à présent que chaque élément $2 \leq \alpha \leq n^3 + n$ apparaît au plus deux fois dans le tableau qui décrit $\circ$. $\forall \alpha : n^3 + 1 \leq n^3 + n$, le couple $\tuplTwo{i}{j}$ tel que $i \circ j = \alpha$ est unique. En effet, il n'y a que $n^3 + k$ dans la définition de $\circ$ qui soit supérieur à $n^3$ et $\forall k \in \range{n}$, un seul $j$ existe tel que $j = kn^2$. $\forall \alpha : 2 \leq \alpha \leq n^3$, outre $i \circ j = 1$, les deux conditions restantes sont mutuellement exclusive, $\alpha$ peut donc être le résultat d'au plus deux produits distincts. On doit aussi montrer que la réduction préserve l'inclusion dans le langage. C'est-à-dire qu'on veut $x \in \Gen \iff \fofOne{f}{x} \in \GenT{2}$. Il suffit de simplifier un $\fofOne{f}{x}$ sans changer le fait que le dernier élément $n^3 + n$ est dans la fermeture de $\setOne{1}$ selon $\circ$. Première simplification, on retire l'unicité des éléments dans la section du carré, $\paren{\paren{i - n^3 \bullet j - n^3} - 1} n^2 + \paren{i - n^3 - 1} n + \paren{j - n^3}$ devient donc $\paren{i - n^3 \bullet j - n^3} n^2$. On retire donc la "cascade" des $1 \circ j = j + 1$ de la fermeture de $\setOne{1}$ selon $\circ$, si et seulement si cette dernière incluait un élément $\alpha$ c'est toujours le cas parce qu'à présent on le génère directement. Seconde simplification, on retire tout simplement les "cascades" qui ne sont plus utilisées, ceci ne change pas la fermeture de $\setOne{1}$ selon $\circ$. On se retrouve donc avec une opération $i \circ j$ modifiée: \[ \begin{cases} n^3 + k & \text{si } i = 1 \text{ et } \exists k \in \range{n} : j = kn^2\\ \paren{i - n^3 \bullet j - n^3} n^2 & \text{si } i,j > n^3\\ 1 & \text{sinon} \end{cases} \] Cette dernière opération est semblable à $\bullet$ décrite par $x$. En effet, $i \bullet j = \alpha \iff i + n^3 \bullet j + n^3 = \alpha n^2 \text{ et } 1 \circ \alpha n^2 = n^3 + \alpha$. Donc, $n$ est dans la fermeture de $\setOne{1}$ selon $\bullet$ si et seulement si $n^3 + n$ est dans la fermeture de $\setOne{1}$ selon notre $\circ$ modifié. \end{proof} %\section{Restrictions Ligne} % %Il y a aussi GEN-1-LIGNE, GEN-1-PPT et GEN-LIGNE-PPT (conjonction de deux restrictions). % %\begin{itemize} %\item On a évidemment GEN-1-LIGNE $\leq$ GEN-LIGNE, on voudrait aussi GEN-LIGNE $\leq$ GEN-1-LIGNE (avec réduction plus petite que log) %\item GEN-1-LIGNE est L-complet selon $NC^1$ (GEN-1-LIGNE $\reducNC$ GEN-LIGNE avec GEN-LIGNE dans L) et (DCA $\reducNC$ GEN-1-LIGNE avec DCA L-complet selon $NC^1$) %\item On sait GEN-LIGNE $\equiv$ STCONN-OUTDEG1, donc GEN-LIGNE est L-complet selon \dots (manque à savoir quelle réduction j'avais utilisé\dots) %\item On a évidemment GEN-LIGNE-PPT $\leq$ GEN-LIGNE, mais aussi GEN-LIGNE $\leq$ GEN-LIGNE-PPT car si l'arbre de preuve existe c'est une ligne (donc la taille est poly). Donc GEN-LIGNE-PPT n'est pas intéressant. %\item GEN-1-Ligne(2) $\subseteq$ GEN-1-TailleTemoin(poly) %\item $\forall c \in \N$, GEN-Ligne(c) $\in \NLClass$ %\item $\forall c \in \N$, GEN-Ligne(c) hard pour $\NLClass$ %\end{itemize} % %\begin{defn}\cite{BM91} $\GenRangee{\fofOne{t}{n}}$\\ %Même problème que $\Gen$ avec une restriction sur la donnée: dans le tableau $n \times n$ qui décrit $\bullet$, au plus $\fofOne{t}{n}$ rangées sont non-triviales (une rangée triviale ne contient que des $1$). %\end{defn} \section{Comparer un Témoin de \textsf{Gen} avec les Circuits Booléens} \begin{defn} Soit $f$ une fonction, alors $f$ est \defin{log-constructible} si $\exists M$ un \gls{mT} qui, sur entrée $1^n$, calcule $1^{\fofOne{f}{n}}$ sur son ruban de sortie, en utilisant au plus $\bigO{\fofOne{\log}{n}}$ espace. \end{defn} \begin{defn}Soit $f$ une fonction, \resp{$\GenRTT{f}$}{$\GenRHT{f}$}\\ Donnée: Un tableau $n \times n$ qui décrit une opération binaire $\bullet$ sur $\range{n}$ et un sous-ensemble $R \subseteq \range{n}$.\\ Question: Est-ce que $\exists$ un témoin de $n \in \closure{R}{\bullet}$ de \resp{taille}{hauteur} au plus $\fofOne{f}{n}$? \end{defn} \begin{prop}\label{prop-genrht-nauxpda} \sloppy Soit $f \in \bigOmega{\fofOne{\log}{n}}$ et log-constructible, alors $\GenRHT{f} \in \NAuxPDA{2^{\bigO{\fofOne{f}{n}}}}{\bigO{\fofOne{\log}{\fofOne{f}{n}} + \fofOne{\log}{n}}}$. \end{prop} \begin{proof} \newcommand{\ParcoursTemoin}[2]{\fofTwo{\textsc{ParcoursTémoin}}{#1}{#2}} Soit $\bullet$ une opération binaire sur $\range{n}$, $R$ un sous-ensemble non-vide de $\range{n}$. Avant de construire une \gls{AuxNPDA} $A$ qui décide si $\exists$ un témoin de $n \in \closure{R}{\bullet}$ de hauteur au plus $\fofOne{f}{n}$, il faut définir $\ParcoursTemoin{h}{k}$. %Soit $k \in \range{n}$, alors un \defin{pseudo-témoin} de $k \in \closure{R}{\bullet}$ est un témoin de $k \in \closure{R}{\bullet}$ excepté qu'il est possible d'avoir $s$ une feuille telle que $\fofOne{\lambda}{s} \notin R$. %Pour uniquement identifier un pseudo-témoin d'hauteur au plus $h$, il suffit d'indiquer les enfants de chaque sommet interne $k$ en préordre. On a donc une séquence $C$ d'au plus $2^h - 1$ paires $\tuplTwo{i}{j}$. %Afin de déterminer si un pseudo-témoin $T$ est aussi un témoin, on effectue un simple parcours en profondeur (voir par exemple \cite[Chapitre~20]{CLRS22}) du pseudo-témoin décrit par une séquence $C$ donnée. Pour décrire un témoin de hauteur au plus $\fofOne{f}{n}$, il suffit d'une séquence $C$ d'au plus $2^{\fofOne{f}{n}} - 1$ paires de $\tuplTwo{i}{j} \in \range{n}^2$, chacune représentant les enfants d'un sommet interne du témoin. Afin de déterminer si un $C$ donné -- qu'on peut imaginer sur un ruban en lecture seule avec sa propre tête -- décrit un témoin de $n \in \closure{R}{\bullet}$ de hauteur au plus $\fofOne{f}{n}$, un algorithme accepte si $\ParcoursTemoin{\fofOne{f}{n}}{n}$ ne refuse pas, où $\ParcoursTemoin{h}{k}$ est: %L'algorithme $\ParcoursTemoin{h}{k}$ effectue son calcul récursif avec un accès de lecture global à un $C$ quelconque. %Un témoin de $k \in \closure{R}{\bullet}$ de hauteur au plus $\fofOne{f}{n}$ peut être décrit par une séquence les enfants de chaque sommet interne $k$ en préordre %L'algorithme déterministe effectue un simple parcours en profondeur (voir par exemple \cite[Chapitre~20]{CLRS22}) %On pose la procédure $\ParcoursTemoin{h}{k}$, \begin{algorithmic}[1] \Procedure{ParcoursTémoins}{$\lstTwo{h}{k}$} \If{$k \notin R$} \State $\lstTwo{i}{j} \gets$ Prochaine paire $\tuplTwo{i}{j}$ dans $C$\label{algo-genrht-nauxpda-nd} \If{$h = 0$ ou $i \bullet j \neq k$} \State arrêt de l'algorithme et refus \Else \State $\ParcoursTemoin{h - 1}{i}$ \State $\ParcoursTemoin{h - 1}{j}$ \EndIf \EndIf \EndProcedure \end{algorithmic} %Étant donné que $\ParcoursTemoin{h}{k}$ effectue un simple parcours en profondeur (voir par exemple \cite[Chapitre~20]{CLRS22}), on suppose que si $C$ décrit un témoin de $n \in \closure{R}{\bullet}$ de hauteur au plus $\fofOne{f}{n}$, alors l'algorithme accepte. On pose $\Predi{0}{h}$ vérifié si $\forall k \in \range{n}$ tel que $\nexists$ un témoin de $k \in \closure{R}{\bullet}$ de hauteur au plus $h$, $\ParcoursTemoin{h}{k}$ refuse $\forall$ séquence $C$ donnée. Dans le cas de base et le pas inductif, on a $k \notin R$ sinon il existerait un témoin d'hauteur $0$. Pour $\Predi{0}{0}$, on a donc un refus peu importe $C$ parce que $h = 0$. Pour $\Predi{0}{h + 1}$, on suppose que la paire $\tuplTwo{i}{j}$ est telle que $i \bullet j = k$, sinon le prédicat est immédiatement vérifié. Étant donné que $\nexists$ un témoin de $k \in \closure{R}{\bullet}$ de hauteur au plus $h + 1$, on doit avoir $\nexists$ un témoin de $i$ ou $j \in \closure{R}{\bullet}$ de hauteur au plus $h$ (on suppose sans perte de généralité que c'est $i$). Par hypothèse d'induction, on a que $\ParcoursTemoin{h}{i}$ refuse $\forall$ séquence $C$ donnée. On pose $\Predi{1}{h}$ vérifié si $\forall k \in \range{n}$ tel que $\exists$ un témoin de $k \in \closure{R}{\bullet}$ de hauteur au plus $h$, $\exists$ une séquence $C$ telle que $\ParcoursTemoin{h}{k}$ ne refuse pas. Parce que $h = 0$, on a $\Predi{1}{h}$ étant donné que $k \in R$. Pour $\Predi{1}{h + 1}$, on pose $i$ et $j$ tels que $i \bullet j = k$ et $\exists$ témoins de $\lstTwo{i}{j} \in \closure{R}{\bullet}$ de hauteurs au plus $h$, ce qui est possible sinon on ne pourrait avoir $\exists$ un témoin de $k \in \closure{R}{\bullet}$ de hauteur au plus $h + 1$. Ainsi, on peut supposer que la prochaine paire dans $C$ est $\tuplTwo{i}{j}$ et, par hypothèse d'induction, on a que $\ParcoursTemoin{h}{i}$ et $\ParcoursTemoin{h}{j}$ ne refusent pas. Avec $\Predi{0}{h + 1}$ et $\Predi{1}{h + 1}$ vérifiés, on sait que l'algorithme qui l'utilise accepte \ssi{} $\exists$ un témoin de $k \in \closure{R}{\bullet}$ de hauteur au plus $\fofOne{f}{n}$ et que $C$ est la -- ou l'une des -- séquence qui mène à l'acceptation. %Ainsi, pour une séquence $C$ donnée, $\ParcoursTemoins{\fofOne{f}{n}}{n}$ ne refuse pas \ssi{} le pseudo-témoin décrit par $C$ est un témoin de $n \in \closure{R}{\bullet}$. %L'algorithme est correct car une séquence $C$ pour un pseudo-témoin est acceptée seulement si ce dernier est parcouru en entier sans trouver de sommet interne ... %Afin de simuler cet algorithme sur une \gls{AuxNPDA}, il suffit de remplacer la ligne \ref{algo-genrht-nauxpda-nd} par un choix non-déterministe de $\tuplTwo{i}{j}$ parmi $\lstTwo{i}{j} \in \range{n} : i \bullet j = k$. Maintenant, on construit $A$ qui simule l'algorithme. L'\gls{AuxNPDA} utilise sa pile en tant que pile d'exécution (i.e. \english{call stack}) afin d'effectuer les appels récursifs de $\ParcoursTemoin{h}{k}$. Pour ce qui est de la séquence $C$, celle-ci n'est pas donnée en entrée, mais plutôt construite pendant l'exécution à partir de choix non-déterministe. En effet, on remplace la ligne \ref{algo-genrht-nauxpda-nd} par un choix non-déterministe de $\tuplTwo{i}{j}$ parmi $\range{n}^2$. %Maintenant, on construit $A$ à partir de cet algorithme déterministe en changeant la ligne \ref{algo-genrht-nauxpda-nd} pour un choix non-déterministe de $\tuplTwo{i}{j}$ parmi $\range{n}^2$. Ainsi, $A$ accepte \ssi{} $\exists$ une séquence $C$ qui décrit un témoin de $n \in \closure{R}{\bullet}$ de hauteur au plus $\fofOne{f}{n}$. Avant de calculer les bornes d'espace et de temps de $A$, on note $\exists \lstTwo{\alpha_1}{\alpha_2} \in \N$ tels que $\forall$ mot $w \in \Sigma^*$ qui encode $\bullet$ et $R$, $\len{w} \leq \alpha_1 n^{\alpha_2}$. Le temps de calcul de $A$ est principalement borné par la taille du témoin $\in 2^{\bigO{\fofOne{f}{n}}}$. Pour chaque sommet, $A$ doit -- outre l'arithmétique et la lecture du ruban -- empiler et dépiler le cadre d'exécution (i.e. \english{stack frame}) de $\ParcoursTemoin{h}{k}$ qui est de taille $\in \bigO{\fofOne{\log}{\fofOne{f}{n}} + \fofOne{\log}{n}}$ afin de mémoriser $h$, $i$ et $j$. Un petit détail est que $A$ doit calculer $\fofOne{f}{n}$ en temps $2^{\bigO{\fofOne{\log}{n}}}$, ce qui ne change pas la borne car $f \in \bigOmega{\fofOne{\log}{n}}$. La borne supérieure du temps de calcul est donc $2^{\bigO{\fofOne{f}{\len{w}}}}$. Étant donné que $A$ réutilise son espace pour simuler chaque appel de $\ParcoursTemoin{h}{k}$ et qu'on sait que la taille de ceci est $\in \bigO{\fofOne{\log}{\fofOne{f}{n}} + \fofOne{\log}{n}}$. L'espace utilisé pour calculer $\fofOne{f}{n}$ ne change pas la borne d'espace non plus. La borne supérieure d'espace est donc $\bigO{\fofOne{\log}{\fofOne{f}{\len{w}}} + \fofOne{\log}{\len{w}}}$. Pour finir, on a que $A$ accepte \ssi{} $\exists$ une séquence $C$ qui décrit un témoin de $n \in \closure{R}{\bullet}$ de hauteur au plus $\fofOne{f}{n}$. Avec les bornes de temps et d'espace calculées plus haut, on a $\GenRHT{f} \in \NAuxPDA{2^{\bigO{\fofOne{f}{n}}}}{\bigO{\fofOne{\log}{\fofOne{f}{n}} + \fofOne{\log}{n}}}$. % equiv du non-determinisme comparé à C % implementation de l'algo, empile chaque cadre d'appel de fonction sur la pile. Vérifier le temps de calcul et l'espace de chaque cadre. %\begin{algorithmic}[1] %\State Empiler $\tuplTwo{n}{\fofOne{\log^\alpha}{n}}$ %\While{pile non vide} % \State $\lstTwo{k}{h} \gets$ Dépiler\label{algo-genrht-nauxpda-depile} % % \If{$k \notin R$}\label{algo-genrht-nauxpda-if} % \If{$h = 0$ ou $\nexists \lstTwo{i}{j} \in \range{n} : i \bullet j = k$} % \State $A$ s'arrête et refuse % \Else % \State $\lstTwo{i}{j} \gets$ Choix non-déterministe parmi $\forall \lstTwo{i}{j} \in \range{n} : i \bullet j = k$ % \State Empiler $\tuplTwo{i}{h - 1}$ % \State Empiler $\tuplTwo{j}{h - 1}$ % \EndIf % \EndIf %\EndWhile %\State $A$ s'arrête et accepte %\end{algorithmic} %Cet algorithme explore de potentiels témoins de $n \in \closure{R}{\bullet}$ en profondeur. On a donc qu'avec $h$ à la ligne \ref{algo-genrht-nauxpda-if}, peu importe les choix non-déterministes, il reste au plus $2^h$ exécutions de boucle (le nombre maximal de descendants d'une arborescence binaire). Étant donné que le temps de calcul d'une boucle est $\in n^{\bigO{1}}$, le temps de calcul de $A$ sur $w$ est $\in 2^{\fofOne{\log^\alpha}{n}} n^{\bigO{1}} \subseteq 2^{\bigO{\fofOne{\log^\alpha}{n}}}$. % %\renewcommand{\Pred}[2]{\fofTwo{\mathrm{P}}{#1}{#2}} %\renewcommand{\Predi}[3]{\fofTwo{\mathrm{P}_{#1}}{#2}{#3}} % %\newcommand{\PredT}[2]{\Predi{\mathrm{t\acute{e}moin}}{#1}{#2}} %\newcommand{\PredC}[2]{\Predi{\mathrm{config}}{#1}{#2}} % %On utilise la notion de configuration et de paire de configurations réalisable dans \cite{C71a}. % %Soit $\Pred{k}{h}$ vérifié si $\PredT{k}{h} \iff \PredC{k}{h}$, où $\PredT{k}{h}$ est vérifié si $\exists$ témoin de $k \in \closure{R}{\bullet}$ avec hauteur au plus $h$ et $\PredC{k}{h}$ est vérifié si $\forall$ configuration $C_1$ à la ligne \ref{algo-genrht-nauxpda-if} avec $\lstTwo{k}{h}$, $\exists$ configuration $C_2$ à la ligne \ref{algo-genrht-nauxpda-if} avec $k' \in R$ et $\tuplTwo{C_1}{C_2}$ réalisable. % %On démontre par induction sur $h$ que $\forall k \in \range{n}, \Pred{k}{h}$. % %On a $\PredT{k}{0} \iff \PredC{k}{0}$ car avec $k \in R$, $\tuplTwo{C_1}{C_1}$ est immédiatement réalisable et avec $k \notin R$, $A$ refuse parce que $h = 0$. Parce que $\PredT{k}{h + 1} \iff \exists \lstTwo{i}{j} \in \range{n} : i \bullet j = k$ et $\PredT{i}{h} \wedge \PredT{j}{h}$, on a que, par hypothèse d'induction, $\PredT{k}{h + 1} \iff \PredC{k}{h + 1}$. En effet, si $\exists \lstTwo{i}{j} \in \range{n} : i \bullet j = k$ et $\PredC{i}{h} \wedge \PredC{j}{h}$ alors $A$ va dépiler $\tuplTwo{j}{h}$ puis $\tuplTwo{i}{h}$ pour atteindre une configuration $C_2$ telle que $k' \in R$, sans jamais dépiler plus bas qu'en $C_1$, la configuration où on avait $\lstTwo{k}{h + 1}$ à la ligne \ref{algo-genrht-nauxpda-if}. Sinon, soit $\nexists \lstTwo{i}{j} \in \range{n} : i \bullet j = k$ alors $A$ refuse, soit (on choisit $i$ sans perte de généralité) $\exists \lstTwo{i}{j} \in \range{n} : i \bullet j = k$ mais $\neg \PredC{i}{h}$ alors $\PredC{k}{h + 1}$ est impossible car $A$ dépasse la profondeur de pile permise (vu que $A$ termine en temps fini). % %Si $w \in \GenRHT{f}$ alors $\PredT{n}{\fofOne{f}{n}}$ donc $\exists$ une suite de choix non-déterministes telle que $A$ quitte la boucle pour s'arrêter en acceptant. Sinon, $\neg \PredT{n}{\fofOne{f}{n}}$ donc aucune suite de choix non-déterministes mène à une pile qui permet à $A$ de quitter la boucle et, parce que $A$ termine en temps fini, $A$ s'arrête et refuse. % %Donc, $A$ décide $\GenRHT{f}$ en temps $2^{\bigO{\fofOne{\log^\alpha}{n}}}$ et, parce chaque opération réutilise le même espace, en espace $\bigO{\fofOne{\log}{n}}$, peu importe les choix non-déterministes. \end{proof} \begin{cor}\label{cor-genrtt-nauxpda} \sloppy Soit $f$ une fonction log-constructible et constructible en temps, alors $\GenRTT{f} \in \NAuxPDA{\bigO{\fofOne{f}{n}}}{\bigO{\fofOne{\log}{\fofOne{f}{n}} + \fofOne{\log}{n}}}$. \end{cor} \begin{proof} \newcommand{\ParcoursTemoin}[2]{\fofTwo{\textsc{ParcoursTémoin}}{#1}{#2}} Afin d'appliquer la démonstration de la proposition \ref{prop-genrht-nauxpda} à $\GenRTT{f}$, il faut effectuer deux changements. On réutilise le résultat que $\ParcoursTemoin{h}{k}$ ne refuse pas si $\exists$ un témoin de $k \in \closure{R}{\bullet}$ de hauteur au plus $h$ et que la bonne séquence $C$ est donnée et refuse s'il n'existe pas de tel témoin, peu importe la séquence $C$ donnée. Étant donné que $\fofOne{f}{n}$ représente ici la taille et non la hauteur, la simulation directe de l'algorithme est incorrecte car elle accepte les mots où $\exists$ un témoin de $n \in \closure{R}{\bullet}$ de taille entre $\fofOne{f}{n}$ et $2^{\fofOne{f}{n}}$. La solution est que $A$ doit compter le nombre d'appels de $\ParcoursTemoin{h}{k}$ -- le nombre de sommets du témoin parcourus -- et refuser dès que ce compte excède $\fofOne{f}{n}$. L'autre changement est le temps de calcul. Étant donné que la taille du témoin est maintenant $\bigO{\fofOne{f}{n}}$ ceci devient la nouvelle borne supérieure. La borne sur l'espace est inchangée puisque $\bigO{\fofOne{\log}{\fofOne{f}{n}} + \fofOne{\log}{n}}$ inclut déjà l'espace requit pour le compteur du nombre de sommets parcourus $\fofOne{\log}{\fofOne{f}{n}}$. %Afin de corriger le fait que $A$ accepte les mots %En plus de simuler le même algorithme vu plus haut, $A$ doit aussi compter le nombre d'appel de $\ParcoursTemoin{h}{k}$ -- le nombre de sommet du témoin parcouru -- et refuser dès que ce compte excède $\fofOne{f}{n}$. Il est donc possible de réutiliser le même argument que $\ParcoursTemoin{h}{k}$ refuse \ssi{} %On pose $A$ une \gls{AuxNPDA} qui exécute le pseudo-algorithme suivant, sur entrée $w \in \alphabin{n}$, % %\newcommand{\Depiler}{\fofZero{\textsc{Dépiler}}} %\newcommand{\Empiler}[1]{\fofOne{\textsc{Empiler}}{#1}} % %\begin{algorithmic}[1] %\State $\Empiler{n}$ %\State $t \gets \fofOne{f}{n}$ %\While{pile non vide} % \State $k \gets$ \Depiler\label{algo-genrtt-nauxpda-depile} % \State $t \gets t - 1$ % % \If{$k \notin R$}\label{algo-genrtt-nauxpda-if} % \If{$t = 0$ ou $\nexists \lstTwo{i}{j} \in \range{n} : i \bullet j = k$} % \State $A$ s'arrête et refuse % \Else % \State $\lstTwo{i}{j} \gets$ Choix non-déterministe parmi $\forall \lstTwo{i}{j} \in \range{n} : i \bullet j = k$ % \State $\Empiler{i}$ % \State $\Empiler{j}$ % \EndIf % \EndIf %\EndWhile %\State $A$ s'arrête et accepte %\end{algorithmic} \end{proof} \begin{prop}\label{prop-genrht-sac} Soit $\alpha \in \N, f \in \bigOmega{\fofOne{\log^\alpha}{n}}$, alors $\GenRHT{f}$ est $\Hard{\SAC{\alpha}}$ selon $\reducLog$. \end{prop} \begin{proof} Soit $\CircuitFamily{C'}{n}$ la famille de circuit uniforme qui décide un langage $Y \in \SAC{\alpha}$ quelconque. Avant de réellement commencer la preuve, on doit transformer $\forall n \in \N, C'_n$ en un circuit $C_n$ fonctionnellement équivalent. Afin de pouvoir supposer que chaque conjonction est la seule avec sa paire d'arguments, on remplace chaque arête entre un parent $k$ et un de ses enfants $i$, par $k = i \vee 1$. Parce que cette transformation se calcule en espace $\bigO{fofOne{\log}{\len{\codeOne{C'_n}}}}$, on sait que $\CircuitFamily{C}{n}$ est aussi uniforme. On a donc $\exists c \in \N$ tel que $\forall n \in \N$ la profondeur de $C_n$ est d'au plus $c \fofOne{\log^{\alpha}}{n}$. La \gls{mTd} $M_c$ calcule donc sur $w \in \alphabin{n}$ la réduction qui permet d'obtenir $Y \reducLog \GenRHT{f}$. On considère que chaque entrée \resp{$w_i$}{$\neg w_i$} dans $C_n$ est plutôt une constante à valeur \resp{$w_i$}{$\neg w_i$}. On suppose sans perte de généralité que le sommet $N = \len{C_n}$ (celui avec l'identifiant maximum) est le sommet résultat. $M_c$ calcule la description du produit sur $\mathbf{N} = \setcond{\lstTwo{\tuplTwo{0}{k}}{\tuplTwo{1}{k}}}{k \in \range{N^c}}$ tel qu'une conjonction $k = i \wedge j$ devient $\tuplTwo{1}{i} \bullet \tuplTwo{1}{j} = \tuplTwo{1}{k}$, une disjonction $k = k = \bigvee_{j = 1}^m i_j$ devient $\tuplTwo{0}{k} \bullet \tuplTwo{1}{i_j} = \tuplTwo{1}{k}$, et $\tuplTwo{0}{1} \bullet \tuplTwo{1}{N} = \tuplTwo{1}{N^c}$. Pour tous les autres produits, le résultat est $\tuplTwo{0}{1}$. Ce produit sur $\mathbf{N}$ a une définition valide et non-ambiguë. Pour les conjonctions, étant donné que la porte $k$ est l'unique ayant $i$ et $j$ comme arguments, $\tuplTwo{1}{i} \bullet \tuplTwo{1}{j}$ doit être $\tuplTwo{1}{k}$. Pour les disjonctions, même si $i$ est répété comme argument d'une même porte $k$, tous les produits $\tuplTwo{0}{k} \bullet \tuplTwo{1}{i}$ donnent le même résultat. De plus, $\tuplTwo{1}{N}$ ne peut être l'argument d'une porte car $N$ est l'identifiant du sommet résultat, donc $\tuplTwo{0}{1} \bullet \tuplTwo{1}{N}$ doit être $\tuplTwo{1}{N^c}$. On pose $R = \setcond{\tuplTwo{0}{k}}{k \in \range{N}} \cup \setcond{\tuplTwo{1}{k}}{k \text{ identifie un sommet constant } 1}$. Parce que $\CircuitFamily{C}{n}$ est uniforme, $M_c$ sur entrée $w \in \alphabin{n}$ peut calculer la description de $C_n$ en espace logarithmique. Aussi, $\len{C_n} \in n^{\bigO{1}}$ parce que $Y \in \SAC{\alpha}$, donc $\len{\mathbf{N}} = 2 \len{C_n}^c \in n^{\bigO{1}}$. Étant donné la taille polynomiale de la description du produit, $M_c$ sur $w$ utilise un espace $\bigO{\fofOne{\log}{\len{w}}}$. On remarque que la définition du produit est sur l'ensemble $\mathbf{N}$, ce n'est que pour faciliter l'explication. En réalité, $M_c$ opère sur $\range{n'}$ où $n' = 2 N^c$. Par une simple bijection, $\tuplTwo{i}{k}$ devient le nombre $i n + k$. Maintenant que le produit $\bullet$ sur $\mathbf{N}$ et l'ensemble $R$ sont bien définis, il faut démontrer la validité de $M_c$ en tant que réduction de $Y$ à $\GenRHT{f}$. Pour ce faire, on utilise les prédicats $\Predi{0}{h}$ et $\Predi{1}{h}$. Soit $\Predi{0}{h}$ vérifié si $\forall k \in \range{N}, \paren{\text{la valeur du sommet } k \text{ de hauteur au plus } h \text{ est } 0} \implies \paren{\nexists \text{ témoin de } \tuplTwo{1}{k} \in \closure{R}{\bullet}}$. On a $\Predi{0}{0}$ parce qu'un sommet $k$ de hauteur et valeur $0$ est une constante $0$, donc $\tuplTwo{1}{k}$ n'est ni le résultat d'un produit, ni dans $R$. On traite deux cas pour $\Predi{0}{h + 1}$. Si $k = i \wedge j$, alors (sans perte de généralité) le sommet $i$ est de hauteur au plus $h$ et de valeur $0$. Par hypothèse d'induction, $\nexists$ témoin de $\tuplTwo{1}{i} \in \closure{R}{\bullet}$. Parce que $\tuplTwo{1}{k}$ n'est présent qu'en tant que résultat de $\tuplTwo{1}{i} \bullet \tuplTwo{1}{j}$, $\nexists$ témoin de $\tuplTwo{1}{k} \in \closure{R}{\bullet}$. Si $k = \bigvee_{j = 1}^m i_j$, alors tous les sommets $i_j$ sont de hauteur au plus $h$ et de valeur $0$. Par hypothèse d'induction, $\forall i_j, \nexists$ témoin de $\tuplTwo{1}{i_j} \in \closure{R}{\bullet}$. Parce que $\tuplTwo{1}{k}$ ne sont présents qu'en tant que résultats de $\tuplTwo{0}{k} \bullet \tuplTwo{1}{i_j}$, $\nexists$ témoin de $\tuplTwo{1}{k} \in \closure{R}{\bullet}$. Notre second prédicat, $\Predi{1}{h}$, est vérifié si $\forall k \in \range{N}$, (la valeur du sommet $k$ de hauteur au plus $h$ est $1$) $\implies$ ($\exists$ témoin de $\tuplTwo{1}{k} \in \closure{R}{\bullet}$ de hauteur au plus $h$). On a $\Predi{1}{0}$ parce qu'un sommet $k$ de hauteur $0$ et de valeur $1$ est une constante $1$, donc $\exists$ témoin de $\tuplTwo{1}{k} \in \closure{R}{\bullet}$ de hauteur $0$ car $\tuplTwo{1}{k} \in R$. Similairement à $\Predi{0}{h + 1}$, on traite deux cas pour $\Predi{1}{h + 1}$. Si $k = i \wedge j$, alors $\lstTwo{i}{j}$ sont tous deux de hauteur au plus $h$ et de valeur $1$. Par hypothèse d'induction, $\exists$ témoins de $\tuplTwo{1}{i} \in \closure{R}{\bullet}$ et de $\tuplTwo{1}{j} \in \closure{R}{\bullet}$ chacun de hauteur au plus $h$. Parce que $\tuplTwo{1}{i} \bullet \tuplTwo{1}{j} = \tuplTwo{1}{k}$, on a $\exists$ témoin de $\tuplTwo{1}{k} \in \closure{R}{\bullet}$ de hauteur au plus $h + 1$. Si $k = \bigvee_{j = 1}^m i_j$, alors $\exists i_j$ un sommet de hauteur au plus $h$ et de valeur $1$. Par hypothèse d'induction, $\exists$ témoin de $\tuplTwo{1}{i_j} \in \closure{R}{\bullet}$ de hauteur au plus $h$. Parce que $\tuplTwo{0}{k} \bullet \tuplTwo{1}{i_j} = \tuplTwo{1}{k}$, on a $\exists$ témoin de $\tuplTwo{1}{k} \in \closure{R}{\bullet}$ de hauteur au plus $h + 1$. Par $\Predi{1}{h}$, on a donc que la valeur du sommet $N$ est $1$ implique $\exists$ témoin de $\tuplTwo{1}{N} \in \closure{R}{\bullet}$ de hauteur au plus $c \fofOne{\log^{\alpha}}{n}$ et, parce que $\tuplTwo{0}{1} \bullet \tuplTwo{1}{N} = \tuplTwo{1}{N^c}$, implique $\exists$ témoin de $n' \in \closure{R}{\bullet}$ de hauteur au plus $c \fofOne{\log^{\alpha}}{n} + 1$. Ce dernier témoin est donc aussi de hauteur au plus $\fofOne{\log^{\alpha}}{n' = 2 N^c}$, parce que $N = \len{C_n} \geq n$. Puis, $\Predi{0}{h}$ permet de conclure que la valeur du sommet $N$ est $1$ \ssi{} $\exists$ témoin de $n' \in \closure{R}{\bullet}$ de hauteur au plus $\fofOne{\log^{\alpha}}{n'}$. \sloppy Pour conclure, $\forall Y \in \SAC{\alpha}$, $\exists M_c$ tel que $\forall w$, $w \in Y$ \ssi{} $\fofOne{M_c}{w} \in \GenRHT{f}$ et donc, parce que $M_c$ fonctionne en espace logarithmique en $\len{w}$, $Y \reducLog \GenRHT{f}$. \end{proof} \begin{cor}\label{cor-genrht-sac} Soit $\alpha \in \N, f \in 2^{\bigOmega{\fofOne{\log^\alpha}{n}}}$, alors $\GenRTT{f}$ est $\Hard{\SAC{\alpha}}$ selon $\reducLog$. \end{cor} \begin{proof} Le seul changement qu'il faut effectuer par rapport à la proposition \ref{prop-genrht-sac}, est dans le paragraphe précédant la conclusion. On sait que par $\Predi{1}{h}$, la valeur du sommet $N$ est $1$ implique $\exists$ témoin de $n' \in \closure{R}{\bullet}$ de hauteur au plus $\fofOne{\log^{\alpha}}{n'}$. Ce dernier témoin est donc de taille au plus $2^{\fofOne{\log^{\alpha}}{n'}}$. Puis, $\Predi{0}{h}$ permet de conclure que la valeur du sommet $N$ est $1$ \ssi{} $\exists$ témoin de $n' \in \closure{R}{\bullet}$ de taille au plus $2^{\fofOne{\log^{\alpha}}{n'}}$. \end{proof} \begin{cor}\label{cor-genrtt-sac} $\forall \alpha \in \N, \GenRHT{\fofOne{\log^\alpha}{n}}$ est $\Complete{\SAC{\alpha}}$ selon $\reducLog$. \end{cor} \begin{proof} \sloppy Soit $\fofOne{f}{n} = \fofOne{\log^\alpha}{n}$, on a que $f$ est log-constructible car une \gls{mT} -- en espace logarithmique -- peut effectuer une multiplication avec des nombres bornés par $\fofOne{\log^\alpha}{n}$. Ainsi, la proposition \ref{prop-genrht-nauxpda} nous donne $\GenRHT{\fofOne{\log^\alpha}{n}} \in \NAuxPDA{2^{\bigO{\fofOne{\log^\alpha}{n}}}}{\bigO{\fofOne{\log}{n}}}$. Combinée avec \cite{NR95}\cite{V87} qui montre $\SAC{\alpha} = \NAuxPDA{2^{\bigO{\fofOne{\log^\alpha}{n}}}}{\fofOne{\log}{n}}$, on obtient la borne supérieure. Pour la borne inférieure, il suffit d'appliquer directement la proposition \ref{prop-genrht-sac}. \end{proof} \begin{cor} $\forall k \in \N, \GenRTT{n^k}$ est $\Complete{\SAC{1}}$ selon $\reducLog$. \end{cor} \begin{proof} \sloppy Soit $\fofOne{f}{n} = n^k$, on a que $f$ est log-constructible et constructible en temps car une \gls{mT} -- en espace logarithmique -- peut effectuer une multiplication avec des nombres sur $k\fofOne{\log}{n}$ bits. Ainsi, le corollaire \ref{cor-genrtt-nauxpda} nous donne $\GenRTT{n^k} \in \NAuxPDA{\bigO{n^k}}{\bigO{\fofOne{\log}{n}}}$. Combiné avec \cite{NR95}\cite{V87} qui montre $\SAC{1} = \NAuxPDA{2^{\bigO{\fofOne{\log}{n}}}}{\fofOne{\log}{n}}$, on obtient la borne supérieure parce que $\bigO{n^k} \subseteq 2^{\bigO{\fofOne{\log}{n}}}$. Pour la borne inférieure, il suffit d'appliquer directement le corollaire \ref{cor-genrtt-sac}. \end{proof} \section{\textsf{GenPath} Complet pour \textsf{NP}} \begin{defn}\label{def-labeled_graph} Soit $G = \tuplTwo{S}{A}$ un graphe orienté et $f$ une fonction $A \to S$, alors $G = \tuplThree{S}{A}{f}$ est un \defin{graphe orienté avec étiquettes}. \end{defn} %un graphe \resp{orienté}{non-orienté} et \resp{un chemin}{une chaîne} sur les sommets $\lstFour{s_0}{s_1}{\dots}{s_n}$ \begin{note} On encode un graphe $G = \tuplTwo{S}{A}$ avec sa matrice binaire d'adjacence. Le mot $w = \codeTwo{S}{A}$ est donc simplement un tableau de $\cardnSym{S}^2$ bits. Lorsque qu'on doit aussi encoder $f$ la fonction $A \to S$ qui étiquette $G$, on ajoute un tableau de $\cardnSym{S}^2$ nombres chacun sur $\ceil{\fofOne{\log}{\cardnSym{S}}}$ bits. \end{note} \begin{defn}\label{def-chemin_gen} \sloppy Soit $G = \tuplThree{S}{A}{f}$ un graphe orienté avec étiquettes. Alors le chemin (possiblement non-simple) sur les sommets $\lstFour{s_0}{s_1}{\dots}{s_l}$ est \defin{générable} si $\forall i \in \range{l} \fofTwo{f}{s_{i - 1}}{s_i} \in \setFour{s_0}{s_1}{\dots}{s_{i - 1}}$ \end{defn} %\section{Version \textsf{NP}-Complet} \begin{defn}$\GenPath$\\ Donnée: $G = \tuplThree{\range{n}}{A}{f}$ un graphe orienté avec étiquettes.\\ Question: $\exists$ un chemin (possiblement non-simple) \defin{générable} du sommet $1$ au sommet $n$, dans $G$? \end{defn} \begin{prop}\label{prop-genpath-NP} $\GenPath \in \NPClass$. \end{prop} \begin{proof} Voici le calcul de $N$, une \gls{mTnd}, sur $w = \codeThree{\range{n}}{A}{f}$: \begin{enumerate} \item Choisir de manière non-déterministe $l$ parmi $\setFour{0}{1}{\dots}{n^2}$ et l'écrire sur le ruban. \item Choisir de manière non-déterministe un chemin (possiblement non-simple) $C$ sur les sommets $\lstFour{s_0}{s_1}{\dots}{s_l}$ de longueur $l$ de $1$ à $n$ et l'écrire sur le ruban, sinon refuser. \item Accepter si $\forall i \in \range{l} \fofTwo{f}{s_{i - 1}}{s_i} \in \setFour{s_0}{s_1}{\dots}{s_{i - 1}}$, sinon refuser. \end{enumerate} Quels que soient $l$ et $C$, les deux premiers points s'effectuent en $n^{\bigO{1}}$ étapes non-déterministes. Pour un seul $i$, la vérification de $\fofTwo{f}{s_{i - 1}}{s_i} \in \setFour{s_0}{s_1}{\dots}{s_{i - 1}}$ s'effectue en $n^{\bigO{1}}$ étapes déterministes. Ainsi, le dernier point s'effectue aussi en $n^{\bigO{1}}$ étapes déterministes, car il suffit de boucler sur $i \in \range{l}$. On a donc $\exists c \in \N$ tel que $N$ sur toutes entrées $w$, peu importe les choix non-déterministes, fonctionne en temps $\len{w}^c$, parce que $\len{w} \in n^{\bigO{1}}$. %On a que $\len{w} = n^2 + n^2 \fofOne{\log}{n} \in n^{\bigO{1}}$. Il est donc évident que peu importe $l$ et $\tuplFour{s_0}{s_1}{\dots}{s_l}$ choisis, les deux premiers points s'effectuent en $\len{w}^{\bigO{1}}$ étapes non-déterministes. La vérification de $\fofTwo{f}{s_{i - 1}}{s_i} \in \setFour{s_0}{s_1}{\dots}{s_{i - 1}}$ s'effectue en $\len{w}^{\bigO{1}}$ étapes déterministes $\forall i \in \range{n}$, car le chemin est écrit sur le ruban. Donc, le dernier point s'effectue en $\len{w}^{\bigO{1}}$ étapes déterministes, car il suffit de boucler sur $i$. Si $N$ accepte $w = \codeThree{\range{n}}{A}{f}$ alors la suite de choix non-déterministes ayant mené à l'acceptation identifie un chemin de $1$ à $n$ (par le point deux) et que ce dernier est générable (par le point trois). %On suppose par contradiction que $\exists w = \codeThree{\range{n}}{A}{f}$ tel que $\nexists$ un chemin \defin{générable} de $1$ à $n$ dans $G = \tuplThree{\range{n}}{A}{f}$ et que $\exists$ une série de choix non-déterministes tels que $N$ accepte sur $w$. Après ces choix non-déterministes, $N$ aura la représentation d'un chemin valide $\tuplFour{s_0}{s_1}{\dots}{s_l}$ de longueur $l$ écrit sur son ruban. Étant donné que l'étape 3 termine en acceptation, ce chemin est aussi \defin{générable} par définition. Inversement, supposons $w \in \GenPath$. Pour garantir l'acceptation par $N$ nous devons démontrer que si $\exists$ un chemin non-simple générable de $1$ à $n$ de longueur $l > n^2$, alors $\exists$ un chemin (possiblement non-simple) générable de $1$ à $n$ de longueur $l' \leq n^2$. En effet, soit un chemin non-simple générable $C$ de $1$ à $n$ de longueur $l > n^2$, on note $D = \tuplFour{s_0}{s_1}{\dots}{s_l}$ la séquence des sommets traversés par $C$. Alors $\exists t \in S$ tel que $D$ contient $t$ exactement $m > n$ fois. Pour $j \in \range{m}$, on pose $A_j$ l'ensemble des sommets qui précèdent le $j$-ème $t$ dans $D$. Parce que $\opChainFour{\subseteq}{A_1}{A_2}{\dots}{A_m}$, on doit avoir $\exists k \in \range{m - 1} : A_k = A_{k + 1}$. On construit $D'$ en retirant les sommets après le $k$-ème $t$ jusqu'au $t$ suivant, inclusivement. Il existe un nouveau chemin (possiblement non-simple) sur $D'$ celui-ci est de $1$ à $n$ (car on retire un circuit d'un chemin valide) et reste générable (car $A_k = A_{k + 1}$). Ce nouveau chemin est de longueur $l' < l$, si on n'a pas $l' \leq n^2$, il suffit de répéter l'argument jusqu'à ce que ce soit le cas. Ainsi, $\exists$ une suite de choix non-déterministes telle que $N$ accepte sur $w = \codeThree{\range{n}}{A}{f}$ \ssi{} $\exists$ un chemin (possiblement non-simple) générable du sommet $1$ au sommet $n$, dans $G = \tuplThree{\range{n}}{A}{f}$, et refuse sinon. \end{proof} \begin{defn}$\HamPath$\\ Donnée: $G = \tuplTwo{\range{n}}{A}$ un graphe orienté.\\ Question: $\exists$ un chemin hamiltonien du sommet $1$ au sommet $n$, dans $G$? \end{defn} \begin{prop}\label{prop-hampath-reduce-genpath} $\HamPath \reducLog \GenPath$. \end{prop} \begin{proof} Voici comment notre \gls{mTd} $M$ construit $w' = \codeOne{G' = \tuplThree{S'}{A'}{f}}$, à partir de $w = \codeof{\range{n}}{A}$. On explique la construction en deux parties. Le premier sous-graphe de $G'$ est une application de la technique de \textit{timestamp} utilisée dans \cite[Corollaire~25]{J75}, donc $M$ copie les sommets $\range{n}$ initiaux $n$ fois, puis ajoute un arc d'un sommet d'une copie au sommet de la suivante s'il y a un tel arc dans $A$. Formellement: \[ S_1' = \setcond{\tuplTwo{i}{s}_1}{\lstTwo{i}{s} \in \range{n}} \] \[ A_1' = \setcond{\tuplTwo{\tuplTwo{i}{s}_1}{\tuplTwo{i + 1}{t}_1}}{i \in \range{n - 1} \text{ et } \tuplTwo{s}{t} \in A} \] Le second sous-graphe de $G'$ est une suite de gagdets qui permettent d'emprunter $n$ chemin différents pour passer d'un sommet $\tuplTwo{0}{s}_2$ au suivant $\tuplTwo{0}{s + 1}_2$: \[ S_2' = \setcond{\tuplTwo{i}{s}_2}{0 \leq \lstTwo{i}{s} \leq n} \] \[ A_2' = \setcond{\tuplTwo{\tuplTwo{0}{s - 1}_2}{\tuplTwo{i}{s - 1}_2} \text{ et } \tuplTwo{\tuplTwo{i}{s - 1}_2}{\tuplTwo{0}{s}_2}}{\lstTwo{i}{s} \in \range{n}} \] Pour compléter la construction de $G' = \tuplThree{S' = S_1' \bigcup S_2'}{A' = A_1' \bigcup A_2'}{f}$, il faut joindre les deux sous graphes. On ajoute donc à $A'$ l'arc $\tuplTwo{\tuplTwo{n}{n}_1}{\tuplTwo{0}{0}_2}$. On considère le sommet $\tuplTwo{1}{1}_1$ la source et $\tuplTwo{0}{n}_2$ la destination. Le but de chaque gadget est de vérifier que le chemin qui y mène à partir de la source $\tuplTwo{1}{1}_1$ contient une des copies d'un sommet $s$, dans le premier sous-graphe de $G'$. Pour ce faire, la sortie de $f$ est $\tuplTwo{1}{1}_1$ sur toutes entrées sauf: \[ \forall \lstTwo{i}{s} \in \range{n}, \fofTwo{f}{\tuplTwo{i}{s - 1}_2}{\tuplTwo{0}{s}_2} = \tuplTwo{i}{s}_1 \] On note que $M$ ne manipule $G'$ en termes décrits plus haut que sur son ruban de travail. Lorsque $M$ doit écrire un tuple sur son ruban de sortie, elle écrit plutôt un nombre. Donc, $\tuplTwo{i}{s}_1$ devient le nombre $\paren{i - 1} n + s$ et $\tuplTwo{i}{s}_2$ devient le nombre $n^2 + \paren{n - i} n + s + 1$. Cette bijection, calculable en espace $\bigO{\fofOne{\log}{\len{w}}}$, est telle que $\tuplTwo{1}{1}_1$ devient $1$ et $\tuplTwo{0}{n}_2$ devient $n' = 2n^2 + n + 1$, ce qui permet de respecter le format attendu de $\GenPath$. % proof of correctness Avant de procéder à la preuve de correctitude, on note qu'un chemin hamiltonien correspond aussi à une permutation des sommets du graphe. En effet, un tel chemin doit être de longueur $n - 1$. Similairement, un chemin de longueur $n - 1$ est simple \ssi{} il contient tous les sommets du graphe. Démontrons $w \in \HamPath \implies w' \in \GenPath$. On suppose $\exists C$ un chemin hamiltonien sur les sommets $\lstFour{s_1}{s_2}{\dots}{s_n}$ dans $G$ de $s_1 = 1$ à $s_n = n$. Parce que $C$ est simple et de longueur $n - 1$, on sait $\exists C_0$ un chemin sur les sommets $\lstFive{\tuplTwo{1}{s_1}_1}{\tuplTwo{2}{s_2}_1}{\dots}{\tuplTwo{n}{s_n}_1}{\tuplTwo{0}{0}_2}$ dans $G'$ et que celui-ci est générable car l'étiquette de chaque arc impliquée est $\tuplTwo{1}{1}_1$. Parce que $C$ passe par chaque $s \in \range{n}$, on sait que $\forall s \in \range{n}, \exists i \in \range{n}$ tel que $\fofTwo{f}{\tuplTwo{i}{s - 1}_2}{\tuplTwo{0}{s}_2} = \tuplTwo{i}{s}_1 \in C$. Donc $\forall s \in \range{n}, \exists i \in \range{n}$ tel que la prolongation de $C_{s - 1}$ par $\tuplTwo{\tuplTwo{i}{s - 1}_2}{\tuplTwo{0}{s}_2}$ demeure un chemin $C_s$ générable. Ainsi $C_n$ est un chemin générable de $\tuplTwo{1}{1}_1$ à $\tuplTwo{0}{n}_2$ dans $G'$. Démontrons $w' \in \GenPath \implies w \in \HamPath$. On suppose $\exists C'$ un chemin générable de $\tuplTwo{1}{1}_1$ à $\tuplTwo{0}{n}_2$ dans $G'$. Un tel chemin doit passer par $\tuplTwo{n}{n}_1$ afin d'accéder au second sous-graphe de $G'$. Donc, avec $s_1 = 1$ et $s_n = n$, $C_0$ un chemin sur les sommets $\tuplFive{\tuplTwo{1}{s_1}_1}{\tuplTwo{2}{s_2}_1}{\dots}{\tuplTwo{n}{s_n}_1}{\tuplTwo{0}{0}_2}$ est le préfixe de $C'$. On a bien $\len{C_0} = n$ promis par la technique de \textit{timestamp}. Afin de se rendre à $\tuplTwo{0}{n}_2$, $C'$ doit inclure un arc avec destination $\tuplTwo{0}{s}_2$ et ce $\forall s \in \range{n}$. Les seuls arcs avec $\tuplTwo{0}{s}_2$ comme destination, sont $\forall i \in \range{n}, \tuplTwo{\tuplTwo{i}{s - 1}_2}{\tuplTwo{0}{s}_2}$ et donc $C'$ doit contenir un de ceux-ci. $C'$ est aussi générable, il est donc nécessaire que $\forall s \in \range{n}, \exists i \in \range{n}$ tel que $C_0$ passe par $\fofTwo{f}{\tuplTwo{i}{s - 1}_2}{\tuplTwo{0}{s}_2} = \tuplTwo{i}{s}_1$. On a donc $\exists C$ un chemin de longueur $n - 1$ tel que $\forall s \in \range{n}$, $C$ passe par $s$, donc hamiltonien, de $1$ à $n$ dans $G$. % proof that it is computed in logspace Les conditions dans les définitions de $S'$, $A'$ et $f$ se décident en espace $\bigO{\fofOne{\log}{\len{w}}}$. Puisque le calcul de chaque arc (pour l'écrire en sortie dans $A'$ et écrire son étiquette dans $f$) ne dépend que du sommet source et destination, on peut réutiliser cet espace logarithmique. Finalement, il suffit de répéter ce calcul un nombre proportionnel à $\cardnSym{A'}$, ce qui reste polynomial en $\len{w}$. Ainsi, $M$ calcul $w'$ en espace $\bigO{\fofOne{\log}{\len{w}}}$ tel que $w \in \HamPath \iff w' \in \GenPath$. \end{proof} \begin{cor} $\GenPath$ est $\Complete{\NPClass}$ selon $\reducLog$ \end{cor} \begin{proof} On sait transformer la réduction $\reducP$ dans \cite{C71b} et \cite[Chapitre~7.5]{Si12} afin d'obtenir $\TSAT$ est $\Complete{\NPClass}$ selon $\reducLog$. Similairement, on peut obtenir $\TSAT \reducLog \HamPath$ à partir de \cite{K72} et \cite[Chapitre~7.5]{Si12}. On a donc, par la proposition \ref{prop-hampath-reduce-genpath} et la transitivité de $\reducLog$, que $\HamPath$ est $\Hard{\NPClass}$ selon $\reducLog$. Avec la proposition \ref{prop-genpath-NP}, on obtient la complétude. \end{proof} %\section{Version \textsf{P}-Complet} % %\begin{todo} %Transcrire la définition de mes notes %\end{todo} % %\begin{defn}$\GenPathRelax$\\ %Donnée: $G = \tuplThree{\range{n}}{A}{f}$ un graphe orienté avec étiquettes.\\ %Question: $\dots$ %\end{defn} % %\begin{prop}\label{prop-genpathrelax-P} %$\GenPathRelax \in \PClass$ %\end{prop} % %\begin{todo} %Preuve (Visiter l'idée de Multi-GEN (i * j = vecteur one-hot de [n])). % %GENPATH-RELAX : difficile à définir, mais on autorise d'utiliser un edge avec un certain label, s'il existe un chemin légal quelconque qui part de $s$ vers ce label. % %On pense que GENPATH-RELAX $\equiv$ GEN symétrique, on aurait donc P-complétude (faut juste que j'écrive la preuve formellement) %\end{todo} % %