915.tex

\documentclass{agregfiche}

\title{Leçon 915 -- Classes de complexité. Exemples}


% V1 par Aliaume Lopez
% Relu par Gaetean Doueneau, Aliaume Lopez, Emilie Grienberger, Charlie Jacomme
% Relu par Jean Goubault

\begin{document}

\maketitle

\secrapports
\begin{rapport}{2019}

Le jury attend que le candidat aborde à la fois la complexité en temps et en
espace. Il faut naturellement exhiber des exemples de problèmes appartenant aux
classes de complexité introduites, et montrer les relations d’inclusion
existantes entre ces classes, en abordant le caractère strict ou non de ces
inclusions. Le jury s’attend à ce que les notions de réduction polynomiale, de
problème complet pour une classe, de robustesse d’une classe vis à vis des
modèles de calcul soient abordées. Se focaliser sur la décidabilité dans cette leçon
serait hors sujet.

\end{rapport}

\begin{rapport}{2017,2018}
 [Parler de] décidabilité dans cette leçon serait hors sujet.
\end{rapport}

\secindispensables

\begin{itemize}
    \item Complexité en espace et en temps.
    \item Les classes usuelles ($\P$, $\NP$, $\PSPACE$) et inclusions.
    \item Notion de réduction, de problème complet
    \item SAT et le théorème de Cook

%    \item Le problème "classiquement complet"
%        \begin{equation}
%            L = \left\{ (M, x, 1^t) ~|~ \langle M, x \rangle \text{ termine en
%                temps (resp. espace) }\leq t
%            \right\}
%        \end{equation}

\end{itemize}

\secasavoir

\begin{itemize}
	\item Exemples de problèmes complets sur des
          domaines différents (graphes, automates,
          grammaires, logique, circuits)
        \item Exemples de réductions.
	\item La robustesse vis-à-vis du modèle de calcul (une bande, plusieurs
          bandes, écriture sur entrée)
	\item Savitch et les classes en espace
        \item Modèle des machines RAM
        \item Les théorèmes de hiérarchie stricte (attention, la preuve concernant l'espace est très difficile, dangereux en développements)
\end{itemize}


\secidees

\begin{itemize}
    \item Des théorèmes de borne inférieure de simulation
      (une bande vs deux bandes en $O(n)$ vs $O(n^2)$
      pour le langage des palindromes).
    \item Les classes $\NL$, $\coNL$ et Immerman-Szelepcsényi
    \item Développer le côté logique (2SAT, HORNSAT, SAT, QBF, CTLSAT).
    \item Les classes alternantes, le lien avec
      $\PSPACE$ et $\EXP$ et la hiérarchie polynomiale [Car]
    \item Une machine qui calcule trop rapidement est un automate
      [Car]
    \item (vraiment loin du programme) Classes randomisés (tests de primalité, algorithme de Berlekamp,
      polynomial identity testing, RP, coRP)

\end{itemize}

\secpieges

\begin{itemize}
    \item Attention à la représentation des données.
    \item Mettre des exemples, et des exemples.
    \item Ne pas centrer toute la leçon sur $\P$ et $\NP$, mais ne pas les oublier.
    \item Un petit diagramme qui permet de s'y retrouver
      en annexe avec les inclusions strictes et les égalités est le bienvenu.
    \item Si on parle de $\NL$, bien formaliser le type de machines
        considérées,  et bien expliquer la notion de réduction polynomiale,
        et logarithmique si on parle de $\NL$
    \item Les différentes ouvertures hors programme peuvent être très dangereuses, le domaine de la complexité est plein de pièges et de subtilités.


\end{itemize}


\secquestionsclassiques

\begin{itemize}
    \item En pratique, que signifie $NP$-complet ? Quelle est
      l'intérêt de la théorie de la complexité ?
% problème intractable => heuristique
    \item Quels sont les impacts de la variation du modèle sur la
    complexité ?
%     faible, c'est l'intéret des TM
    \item Pourquoi utiliser le formalisme des machines de Turing
        plutôt qu'un autre (RAM, $\lambda$-calcul, fonctions
        récursives) ?
%         cf au dessus
    \item Citer une classe qui n'est pas $P$, $NP$ ou $PSPACE$.
%     L
    \item Montrer que tel problème $X$ est $C$-complet.
    \item Comment varie la complexité en fonction de la taille de
    l'alphabet ?
%    polynomialement, c'est le speed up theorem
    \item Discussions sur les variantes de SAT.
\end{itemize}

\secreferences

\begin{itemize}
    \item \input{refs/perifel}
    \item \input{refs/carton}
      \textit{La $NP$-complétude de HamPATH est fausse dedans. Le \bsc{Kleinberg} la fait bien par contre.}
    \item \input{refs/arorabarak}
    \item Éviter le \bsc{Papadimitriou}, qui contient de très nombreuses
fausses preuves.
\end{itemize}

\secdev

\begin{itemize}
    \item[++] \input{dev/cook}
    \item[++] Preuve de complétude d'un problème au choix.
    \item[+] \input{dev/immerman}
    \item[+-] \input{dev/CNFformula}
%    \item \temporary{Équivalence entre 2 bandes et k bandes}
%    \item \temporary{Hiérarchie en temps et en espace}
%    \item \temporary{Universalité d'un langage rationnel est PSPACE complet}
\end{itemize}


\end{document}

%%% Local Variables:
%%% mode: latex
%%% TeX-master: t
%%% End: