main.tex

\documentclass[12pt]{article}

\input{inc.tex}

\usepackage{mathrsfs}
\usetikzlibrary{positioning}
\usepackage{tikz-cd}
\usepackage{ebproof}
\newcommand\M{\text{M}(X\uplus X^{-1})}
\newcommand\G{\mathscr{G}(X)}
\renewcommand\F{\mathscr{F}(X)}
\newcommand\V{\mathbb{V}}
\newcommand\E{\mathbb{E}}
\newcommand\D{\mathbb{D}}
\newcommand\bet{\rightarrow_\beta}
\newcommand\beq{=_\beta}
\newcommand\Rel{\text{Rel}}
\newcommand\Set{\text{Set}}
\newcommand\Oper{\text{Oper}}
\newcommand\Inv{\text{Inv}}
\newcommand\Pol{\text{Pol}}
\renewcommand\P{\mathscr{P}}
\newcommand\ar{\text{ar}}
\newcommand\arf{\text{ar}}
\newcommand\csp{\text{CSP}}
\renewcommand\C{\mathscr{C}}
\newcommand\fset{\text{FinSet}}
\newcommand\ffun{\text{FinFun}}
\newcommand\im{\text{Im }}
\newcommand\sem[1]{\llbracket {#1} \rrbracket}
\newcommand\ext{\text{Ext}}
\newcommand\fns{\mathscr{F}}
\newcommand\brk[1]{[ {#1} ]}
\newcommand\psh{\text{PSh}}
\newcommand\sh{\text{Sh}}
\newcommand\shc{\text{Sh}_\text{can}}
\newcommand{\tproof}[1]{{\scantokens{\begin{prooftree}#1\end{prooftree}}}}
\newcommand{\cf}{\mathbb{F}}
\newcommand{\tsigma}{\widetilde{\Sigma}}
\newcommand{\tgamma}{\widetilde{\Gamma}}
\newcommand{\tlambda}{\widetilde{\Lambda}}
\newcommand{\colim}{\text{colim}}
\newcommand{\fcsp}{\text{FCSP}}
\newcommand{\op}{\text{op}}
\newcommand{\tf}{\widetilde{F}}
\newcommand{\tg}{\widetilde{G}}
\newcommand{\tH}{\widetilde{H}}
\newcommand{\ml}[1]{\langle{#1}\rangle}

\setcounter{tocdepth}{3}

\title{Mémoire de L3~: Une approche catégorique au problème CSP}
\author{Luc Chabassier\and Simon Cabuche}
\date{\small Sous la direction de Damiano Mazza}

\begin{document}

\maketitle

\newpage
\tableofcontents
\newpage

\section*{Remarques générales}

Les annexes contiennent différents résultats et différentes preuves auxquelles
on est arrivé, dont on juge qu'elles ne sont pas nécessaire pour la
présentation des résultats principaux, mais qui peuvent être intéressantes
quand même. On a essayé de s'arranger pour que la lecture des annexes ne soit
pas nécessaire pour la compréhension de notre démarche et de nos résultats,
mais il est possible que certaines preuves fassent référence à des résultats
mis en annexe.

De plus, on considèrera que les entiers sont égaux à leur encodage classique en théorie
des ensembles, à savoir que l'égalité $n = \{0, \dots, n-1\}$ est toujours vraie. On
parlera donc de fonction entre entiers par exemple.


%   ____ ____  ____                    _     _                
%  / ___/ ___||  _ \   _ __  _ __ ___ | |__ | | ___ _ __ ___  
% | |   \___ \| |_) | | '_ \| '__/ _ \| '_ \| |/ _ \ '_ ` _ \ 
% | |___ ___) |  __/  | |_) | | | (_) | |_) | |  __/ | | | | |
%  \____|____/|_|     | .__/|_|  \___/|_.__/|_|\___|_| |_| |_|
%                     |_|                                     
\section{Problèmes de satisfaction de contraintes}\label{secCSP}
\input csp.tex

%   ____      _                        _           _    ____ ____  ____  
%  / ___|__ _| |_ ___  __ _  ___  _ __(_) ___ __ _| |  / ___/ ___||  _ \ 
% | |   / _` | __/ _ \/ _` |/ _ \| '__| |/ __/ _` | | | |   \___ \| |_) |
% | |__| (_| | ||  __/ (_| | (_) | |  | | (_| (_| | | | |___ ___) |  __/ 
%  \____\__,_|\__\___|\__, |\___/|_|  |_|\___\__,_|_|  \____|____/|_|    
%                     |___/                                              
\section{Une catégorie pour les CSP}\label{secCat}
\input sheaves.tex

\section{PP-interprétabilité catégorique}\label{secPP}
\input pp.tex

\section{Conclusion}

Suite à ces travaux, on a presque fini de reformuler en terme de théorie des
catégories les notions et résultats principaux liés à l'étude des CSPs. Une
fois cette reformulation terminée (et surtout le lien entre notre formulation
et la théorie standard mieux compris), il serait intéressant de continuer en
transposant la preuve du théorème de dichotomie des CSPs dans notre
formulation. Notre espoir est qu'une fois cette reformulation finie, on pourra
expliciter précisément les propriétés nécessaires des objets construits, pour
les axiomatiser et voir si on ne peut pas étendre le résultat à une classe plus
large de problèmes.

\section*{Remerciements}

Nous tenons à remercier Damiano Mazza pour nous avoir encadré tout au long du
mémoire et nous avoir permis d'avancer autant.


%     _                               _ _               
%    / \   _ __  _ __   ___ _ __   __| (_) ___ ___  ___ 
%   / _ \ | '_ \| '_ \ / _ \ '_ \ / _` | |/ __/ _ \/ __|
%  / ___ \| |_) | |_) |  __/ | | | (_| | | (_|  __/\__ \
% /_/   \_\ .__/| .__/ \___|_| |_|\__,_|_|\___\___||___/
%         |_|   |_|                                     
\appendix
\newpage
\section{Canonicité}\label{appCanon}
\input canon.tex

\newpage
\section{Approche naïve de catégorie pour les CSP}\label{appNaif}
\input naif.tex

\newpage
\section{Descriptions syntaxiques}\label{appSyn}
\input syntaxic.tex

\newpage
\section{Vision algébrique des CSP}\label{appClones}
\input clones.tex

\newpage
\section{Relèvement sur $\tsigma$}
\input rel.tex

\end{document}