\documentclass[%
  12pt,      % Guide suggests 11pt or 12pt
%  phd        % Thèse de doctorat
%  cotutelle  % Thèse de doctorat en cotutelle
  master     % Mémoire de maîtrise
%  directed   % Travail dirigé (maîtrise)
%  internship % Stage supervisé (maîtrise)
%  ,info      % Enable info mode (prints version and date)
]{udem}

\input{packages}

\input{macros}

\input{glossaire}

\addbibresource{ref.bib}

\graphicspath{{./figures/}}

% Uncomment if there is an index
%\makeindex

%\includeonly{chapters/gen}

\begin{document}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%% METADATA %%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%
%% PDF file metadata
%%
\hypersetup{
  pdftitle    = {Complexité de variantes d'un problème P-complet},
  pdfauthor   = {Jean-Claude Desrosiers},
  pdfsubject  = {Computational Complexity Theory},
  pdfkeywords = {auxiliary pushdown automaton (auxpda),gen problem,logdcfl,multiplex circuit,non-deterministic log-space,polynomial time,proof tree,semi-unbounded fan-in alternating circuits,structural complexity theory,uniform circuit complexity},
}

%%
%% Variable for the info mode (will print version and date in the header)
%%
\version{1.1.0}

%%
%% Variables for title page
%%
\university{Université de Montréal}
%\partner{Other University} % only for cotutelle

\title{Complexité de variantes d'un problème P-complet}
%\subtitle{My subtitle} % optional

\author{Jean-Claude Desrosiers}

\department{Département d'informatique et de recherche opérationnelle}
\faculty{Faculté des arts et des sciences}

\field{informatique}
\specialty{théorique et quantique} % optional

\submit{2026}{Août}

%\copyrightowner{} % automatically set with \author{}
%\copyrightyear{} % automatically set with \submit{}{}

% if using creative commons license, set all three
\ccshort{cc-by}
\cclogo{\ccby}
\ccdeed{https://creativecommons.org/licenses/by/4.0/deed.fr}

% add optional information below the CC license
\moreinfo{Code source et figures du document sont disponibles au \href{https://msc.jclaude.xyz}{msc.jclaude.xyz}}

%%
%% Variables for jury page
%%

% If you need an empty line for <jury member> to write their name on printed paper, then just call \<jury member>{} (e.g. if you want the chair's line to be empty call \chair{})
% Also, you can change <jury member>'s title (e.g. to use the gendered version of the title) otherwise, no need to call the \<jury member>title{}

\chair{Louis Salvail}
%\chairtitle{Présidente rapporteur}

\supervisor{Pierre McKenzie}
%\supervisortitle{Directrice de recherche}

%\cosupervisor{Nom}
%\cosupervisortitle{Codirectrice de recherche}

%\cosupervisortwo{Nom}
%\cosupervisortwotitle{Codirectrice de recherche}

%\cosupervisorthree{Nom}
%\cosupervisorthreetitle{Codirectrice de recherche}

\jurymember{Geňa Hahn}
%\jurymembertitle{Membre du jury}

%\jurymembertwo{Nom}
%\jurymembertwotitle{Membre du jury}

%\jurymemberthree{Nom}
%\jurymemberthreetitle{Membre du jury}

%\examiner{Nom} % required for phd thesis
%\examinertitle{Examinatrice externe}

%\deanrep{Nom}
%\deanreptitle{Représentante du doyen}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%% FRONT MATTER %%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\pagenumbering{arabic}

\expandafter\pdfbookmark[chapter]{\coverpagename}{coverpage}

%%
%% (obligatoire) La page de titre.
%%

\begin{otherlanguage}{french}
\maketitle
\end{otherlanguage}

%%
%% (obligatoire) La page d'identification des membres du jury.
%%

\begin{otherlanguage}{french}
\makejury
\end{otherlanguage}

%%
%% (obligatoire) Le résumé et les mots-clés en français.
%%

\begin{otherlanguage}{french}
\chapter*{Résumé}

Un exemplaire du problème algébrique $\Gen$ est une opération binaire sur les entiers de $1$ à $n$, encodée par un tableau $n \times n$. Étant donné que $1$ est \defin{générable}, la question est de décider si $n$ est générable, où un élément est générable s'il est le résultat de l'opération appliquée à deux éléments générables.

Ce mémoire démontre la complétude de plusieurs variantes naturelles du problème $\Gen$ pour des classes de complexité incluses dans $\PClass$. En développant la notion de témoin d'un exemplaire de $\Gen$ -- un objet analogue à l'arbre de preuve (\english{proof tree}) pour un circuit booléen -- on établit le résultat principal de ce mémoire, soit la complétude d'une variante nommée $\GenT{1}$ pour la classe des langages décidables en espace non-déterministe logarithmique. $\GenT{1}$ empêche tout élément, sauf $1$, d'apparaître plus d'une fois dans le tableau. On propose aussi une variante portant sur la hauteur du témoin d'un exemplaire, qu'on fait correspondre à la profondeur d'un circuit alternant à arité d'entrée semi-illimitée (ou \english{semi-unbounded fan-in alternating circuit}), ainsi qu'une autre qui utilise un graphe orienté et est complète pour $\NPClass$.

Ces preuves reposent en partie sur une révision du circuit multiplex, un modèle de circuit où chaque porte sélectionne un de ses arguments de données selon l'argument guide. De passage, on retravaille de manière plus explicite la preuve connue de l'équivalence entre les langages décidés par un automate à pile auxiliaire et la classe $\LogDCFL$

En conclusion on propose, en s'appuyant sur nos résultats, des pistes de recherche: un candidat $\Complete{\LogDCFL}$, une définition d'uniformité de famille de circuits multiplex exigeant l'ordre topologique et une piste pour analyser le lien entre $\LogDCFL$ et $\NLClass$.

\textbf{Mots-clés:} automate à pile auxiliaire (auxpda), arbre de preuve, circuit alternant, circuit booléen, circuit multiplex, espace non-déterministe logarithmique, logdcfl, problème gen, temps polynomial, théorie de la complexité structurelle
\end{otherlanguage}

%%
%% (obligatoire) Le résumé et les mots-clés en anglais.
%%

\begin{otherlanguage}{english}
\chapter*{Abstract}

An instance of the algebraic problem $\Gen$ is a binary operation on integers between $1$ and $n$, encoded by an $n \times n$ table. Given that $1$ is \defin{generable}, the question is to decide whether $n$ is generable, where an element is generable if it is the result of the operation applied to two generable elements.

This thesis therefore establishes the completeness of several natural variants of the $\Gen$ problem for complexity classes contained in $\PClass$. Using the witness of an instance of $\Gen$ -- an object analogous to the proof tree of a boolean circuit -- we establish a variant named $\GenT{1}$ as a new problem complete for the class of languages decidable in nondeterministic logarithmic space. $\GenT{1}$ forbids any element, except $1$, from appearing more than once in the table. We also propose a variant concerning the height of the witness of an instance, which we match with the depth of a semi-unbounded fan-in alternating circuit, as well as another that uses a graph and is complete for $\NPClass$.

These proofs rely in part on a revision of the multiplex circuit, a circuit model in which each gate selects one of its data inputs according to the steering bits. This also allows us to revisit, more formally, a proof of equivalence between the set of languages decided by an auxiliary pushdown automaton and the class $\LogDCFL$.

In conclusion, building on our results, we propose avenues for future research: a candidate $\Complete{\LogDCFL}$ problem, a definition of uniformity for multiplex circuit families requiring topological order, and an avenue for investigating the link between $\LogDCFL$ and $\NLClass$.

\textbf{Keywords:} alternating circuits, auxiliary pushdown automaton (auxpda), boolean circuit, gen problem, logdcfl, multiplex circuit, non-deterministic log-space, polynomial time, proof tree, structural complexity theory
\end{otherlanguage}

%%
%% (conditionnel) Le résumé et les mots-clés en une autre langue.
%%

%\begin{otherlanguage}{other}
%\chapter*{Abstract}
%
%Lorsque la langue de rédaction du mémoire ou de la thèse est autre que le français ou l’anglais, un résumé dans la langue de rédaction est également requis. Ce résumé doit respecter les normes qui s’appliquent au résumé en français.
%
%\textbf{Keywords:} keywords in other language... (maximum 10 words)
%\end{otherlanguage}

%%
%% (facultatif) Le résumé de vulgarisation.
%%

%\chapter*{Résumé de vulgarisation}
%
%Un tel résumé est facultatif. Il vise à faire connaître les résultats de la recherche au public par l’entremise des médias. Son contenu fournira des informations exactes et des interprétations rigoureuses sur les travaux de recherche, en accordant une attention appropriée aux dimensions éthiques de la recherche et, s’il y a lieu, aux règles se rapportant à l’usage des animaux de laboratoire et à la recherche avec des sujets humains. Il sera rédigé en collaboration étroite avec la direction de recherche, selon les normes de qualité applicables à tout travail de vulgarisation : faire état du contexte, formuler un message clair, utiliser un langage simple et approprié, etc. Le résumé de vulgarisation peut être rédigé en français ou en anglais et ne doit pas dépasser deux pages (au plus 500 mots). Il sera évalué par le jury quant à sa qualité et à son exactitude.

%%
%% (obligatoire) La table des matières, la liste des tableaux, la liste des figures ou autres.
%%

% Table of contents
\cleardoublepage
\pdfbookmark[chapter]{\contentsname}{toc}
\tableofcontents

% List of tables
%\cleardoublepage
%\phantomsection
%\listoftables

% List of figures
\cleardoublepage
\phantomsection
\listoffigures

%%
%% (obligatoire) La liste des sigles et des abréviations.
%%

\printnoidxglossary[title={\acronymsname}]

%%
%% (facultatif) La dédicace.
%%

%\chapter*{Dédicace}
%
%Il s’agit d’un court hommage rendu par l’autrice ou l’auteur à des personnes de son choix. Cet ajout est facultatif, mais autorisé.

%%
%% (facultatif) Les remerciements.
%%

\chapter*{Remerciements}
%
%Les remerciements représentent l’expression d’appréciation ou de reconnaissance envers des personnes ou des organismes et peuvent être exigés de la donatrice ou du donateur, ou de l’organisme subventionnaire.

Je tiens d’abord à remercier Pierre, mon directeur de recherche, pour sa patience, ses précieux conseils et courriels, toujours appréciés, qui ont souvent permis de remettre mes réflexions sur la bonne voie. Je suis également reconnaissant pour son catalogue mental de références, apparemment inépuisable, ainsi que pour son humour, qui a rendu le parcours beaucoup plus agréable.

Je remercie aussi ma famille pour son soutien, ses encouragements et sa confiance tout au long de ce projet. Leur présence a été précieuse, particulièrement dans les moments où l’avancement du mémoire semblait plus difficile.

Enfin, je tiens à remercier ma partenaire pour sa patience et son soutien indéfectible, surtout durant les périodes où l’écriture du mémoire a fait de moi une version nettement moins agréable de moi-même. Merci de m’avoir encouragé et de m’avoir rappelé qu’il existait une vie en dehors de ce mémoire.


%%
%% (facultatif) L’avant-propos.
%%

%\chapter*{Avant-Propos}
%
%L’avant-propos sert à rappeler les raisons qui ont motivé l’autrice ou l’auteur dans son choix de sujet de recherche et de l’approche utilisée pour l’aborder. Il permet de situer l’ouvrage dans le contexte de la discipline ou du champ d’études.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%% MAIN MATTER %%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\cleardoublepage

% first page of each chapter should not be paginated
\removechapterpagination

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%                                                  %
%%   TEXTE DU MÉMOIRE :  introduction page 1,...    %
%%                                                  %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\chapter{Introduction}

%\begin{todo}
%Repasser sur les citation pour ne pas seulement avoir la balise de référence bibliographique, mais aussi le nom d'auteur(s), pour que ce soit tout pareil.
%\end{todo}

La question du lien entre $\PClass$ et $\NPClass$ \cite{C71b} est fondamentale en théorie de la complexité et d'envergure comparable à celle qui la précède de quelques années, toujours sans réponse à ce jour, du lien entre $\LClass$, la classe des langages décidables en espace logarithmique, et $\PClass$ \cite{C69}. En effet, résoudre cette dernière éclairerait la relation entre l'espace et le temps. Évidemment, la problématique a évolué depuis. Notamment, un candidat potentiel pour séparer $\LClass$ de $\LogDCFL$ -- le sous-ensemble de $\PClass$ formé des langages réductibles en espace logarithmique à un \gls{DCFL} -- a été introduit dans \cite{BCMSW09}. Ce candidat est $\TreeEval$, qui s'énonce comme suit : calculer la valeur de la racine d'un arbre où les sommets internes sont des fonctions sur entiers, les feuilles des entiers et la valeur d'un sommet est l'évaluation de sa fonction sur la valeur de ses enfants.

\sloppy La motivation initiale de ce projet de recherche ayant été d'explorer la complexité de $\TreeEval$, le langage complet pour $\PClass$, $\Gen$ \cite{JL76} s'est imposé en tant que problème intéressant en relation avec $\TreeEval$ ainsi qu'en soi. Simplement, un exemplaire du problème algébrique $\Gen$ est une opération binaire sur les entiers de $1$ à $n$, encodée par un tableau $n \times n$. Étant donné que $1$ est générable, la question est de décider si $n$ est générable, où un élément est \defin{générable} s'il est le résultat de l'opération appliquée à deux éléments générables. Ce mémoire démontre donc la complétude de plusieurs variantes naturelles du problème $\Gen$ pour des classes de complexité incluses dans $\PClass$.

Le deuxième chapitre est un préliminaire, qui établit la notation ainsi que les termes et définitions utilisés tout au long du document.

Dans le troisième chapitre, on traite du circuit multiplex, introduit dans \cite{FLR96} et \cite{R97}, où les sommets du circuit sont des portes multiplex chacune ayant un argument guide qui indique lequel des arguments de données est utilisé comme sortie. La simplification du modèle présentée dans ce chapitre nous permet de revisiter la preuve par \cite{MRV99} d'équivalence  entre la classe des languages décidés par un \gls{AuxDPDA} et $\LogDCFL$.

Le quatrième chapitre est le cœur de ce mémoire. On y traite de plusieurs variantes du problème $\Gen$ qui sont complètes pour des classes allant de $\NLClass$ -- les langages décidables en espace non-déterministe logarithmique -- à $\PClass$. Le résultat principal concerne une variante qui restreint les dupliqués dans le tableau représentant l'opération. En effet, si l'on impose la restriction que seul l'entier $1$ peut apparaître plus d'une fois dans le tableau, on obtient $\GenT{1}$, un nouveau problème algébrique complet pour $\NLClass$. Tout aussi surprenant est que la variante devient complète pour $\PClass$ si un doublon de chaque entier est autorisé.

D'autres variantes étudiées restreignent le témoin pour un exemplaire de $\Gen$, un objet analogue à l'arbre de preuve (\english{proof tree}) pour un circuit booléen. En particulier, on démontre l'équivalence entre la hauteur d'un témoin et la profondeur du circuit alternant à arité d'entrée semi-illimitée (ou \english{semi-unbounded fan-in alternating circuit}) -- un circuit booléen où les portes conjonction sont bornées, mais les portes disjonctions ne le sont pas -- qui le décide. Vers la fin du chapitre, on propose $\GenPath$ un problème d'accessibilité de graphe qui s'inspire de $\Gen$ où l'on exige qu'un arc étiquetté puisse être ajoutée au chemin seulement si le sommet associé à cette étiquette est dans le préfixe du chemin. On montre que ce langage est $\Complete{\NPClass}$.

Dans le chapitre final, on propose, en s'appuyant sur nos résultats, des pistes de recherche: un candidat $\Complete{\LogDCFL}$, une définition d'uniformité de famille de circuits multiplex exigeant l'ordre topologique et une piste pour analyser le lien entre $\LogDCFL$ et $\NLClass$.

\include{chapters/preliminaires}

\include{chapters/multiplex}

\include{chapters/gen}

\chapter{Conclusion}

Bien que la preuve d'équivalence détaillée dans ce mémoire entre la classe des languages décidés par un \gls{AuxDPDA} et $\LogDCFL$ ne soit pas nouvelle, le niveau de formalisme avec lequel elle fut traitée dans ce texte l'est. L'observation qu'interdire de combiner ou de séparer un paquet de bits dans un circuit multiplex n'est pas nécessaire afin de conserver la puissance de calcul de la classe $\MuxClass{F_1}{F_2}$ est également nouvelle.

Le problème $\GenT{1}$ discuté n'est pas la première variante de $\Gen$ en lien avec $\NLClass$. En effet, Jones et Laaser \cite{JLL76} montrent que $\STCONN$ se réduit à $\AGen$ -- $\Gen$ où l'opération donnée est associative -- et que $\AGen$ est dans $\NLClass$. L'importante différence est que la preuve de complétude pour $\GenT{1}$ repose sur la notion du témoin. Pour ce qui est de montrer que $\GenT{2}$ est $\Complete{\PClass}$, cela nous donne un problème plus simple à manipuler que $\Gen$ pour démontrer une borne inférieure d'un autre problème.

Le corollaire \ref{cor-genrtt-sac} est similaire à la proposition 3.2 dans \cite{BM91} qui montre qu'un exemplaire de $\Gen$ avec \english{bracketing depth} $\alpha$ -- équivalent à $\GenRHT{\fofOne{\log^\alpha}{n}}$ -- est $\Hard{\NC{\alpha}}$ et inclu dans $\NC{\alpha + 1}$. On a donc un rafinement des bornes, étant donné que $\forall \alpha \in \N, \NC{\alpha} \subseteq \SAC{\alpha} \subseteq \AC{\alpha} \subseteq \NC{\alpha + 1}$.

\section{Pistes Futures}

Une idée intéressante est d'exiger que la description de chaque élément d'une famille de circuits multiplex uniforme respecte un ordre topologique. Un simple ajustement au lemme \ref{lem-DAuxPDAMux} le rendrait conforme à cette nouvelle définition. Ainsi, cette exigence supplémentaire préserve la classe $\MuxClass{n^{\bigO{1}}}{n^{\bigO{1}}}$.

Une piste de travaux futurs serait de généraliser le lemme \ref{lem-DAuxPDAMux} avec des fonctions quelconques. Pour ce faire, il faudrait paramétrer la taille des paquets de bits d'une famille de circuits multiplex. En effet, la borne d'espace du \gls{AuxDPDA} simulé semble en lien direct avec la taille des paquets de bits, on ne peut donc pas introduire un paramètre dans l'un sans faire de même pour l'autre.

\sloppy La question du lien entre $\LogDCFL$ et $\NLClass$ n'est toujours pas résolue (le rapport de Mahajan \cite{MT07} est malheureusement encore d'actualité à cet égard). C'est pourquoi il serait intéressant d'étudier un problème $\GenRTTT{1}{n^{\bigO{1}}}$ combinant les restrictions de $\GenRTT{n^{\bigO{1}}}$ et $\GenT{1}$. En effet, ce nouveau problème semble un bon candidat à la $\LogDCFL$-complétude car l'algorithme qui décide $\GenRTT{n^{\bigO{1}}}$ -- un problème démontré $\Complete{\LogCFL}$ dans le présent mémoire -- pourrait être exécuté de manière déterministe avec la promesse de $\GenT{1}$. On aurait donc deux problèmes similaires qui capturent respectivement $\LogDCFL$ et $\NLClass$.

Bien qu'on ait trouvé un candidat potentiel pour $\Complete{\LogDCFL}$, la situation est différente pour $\TreeEval$. En effet, si l'on pouvait conjecturer la complétude de ce dernier pour $\LogDCFL$ en 2023, une telle conjecture n'est plus viable car Cook et Mertz \cite{CM24} ont prouvé que $\TreeEval$ est dans $\DSpace{\bigO{\fofOne{\log}{n} \fofOne{\log}{\fofOne{\log}{n}}}}$.

Une piste possible pour montrer la $\LogDCFL$-difficulté de $\GenRTTT{1}{n^{\bigO{1}}}$ serait certainement d'utiliser les circuits multiplex comparablement à l'utilisation de circuits semi-bornés pour montrer la $\SAC{1}$-difficulté de $\GenRTT{n^{\bigO{1}}}$.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%% BACK MATTER %%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%
%% (facultatif) Les index.
%%

%\printindex

%%
%% (obligatoire) Les références bibliographiques.
%%

\printbibliography

%%
%% (facultatif) Les annexes.
%%

%\appendix

%\chapter{First Appendix Chapter}

%\chapter{Second Appendix Chapter}

\end{document}

\endinput
% end of file gabarit.tex