\chapter{Considérations de base sur le temps}
\label{temps:chapitre}

Une fois réalisée la formalisation des algorithmes vue au chapitre précédent,
les mathématiciens se sont intéressés à des questions liées au type de
problèmes que l'on pouvait ainsi résoudre (calculabilité). Plus tard, lors de
l'apparition des premiers ordinateurs, la question de l'efficacité de ces
algorithmes s'est posée et le domaine de la complexité algorithmique a vu le
jour.

Dans ce chapitre, nous allons voir les prémices de la complexité, qui
remontent aux années 1960 : définition des classes de complexité en temps,
théorèmes de hiérarchie, relations entre classes, etc. Nous introduirons
également les machines non déterministes et le problème «~$\p=\np$ ?~»
qui a une grande importance depuis les années 1970.

\section{Temps déterministe}

Le modèle des machines de Turing que nous avons vu au chapitre précédent
servira à définir les classes de complexité. Rappelons que le \emph{temps} mis
par une machine $M$ sur une entrée $x$ est le nombre d'étapes du calcul de
$M(x)$ pour arriver à un état final
(définition~\ref{modele:def:temps_espace}). Cela revient en quelque sorte à
mesurer le temps d'exécution de l'algorithme pour résoudre le problème sur
l'entrée $x$, mais on veut une mesure indépendante de la puissance de
l'ordinateur faisant tourner l'algorithme : c'est pourquoi on ne parle pas en
secondes mais en nombre d'étapes de calcul. Grâce à cette notion, nous pouvons
définir des classes de complexité en temps.

\subsection{Classes de complexité en temps}
\index{Classes de complexité!en temps déterministe}%
\begin{recul}%
  Pour la plupart des problèmes, plus la taille de l'entrée est grande, plus
  il faudra du temps pour trouver la solution. Par exemple, il est évident
  qu'on mettra plus de temps à trier une liste d'un million d'éléments plutôt
  qu'une liste de 3 éléments.

  \noindent Il est alors naturel d'évaluer le temps de calcul d'un algorithme
  en fonction de la taille de son entrée. Cette observation donne lieu à la
  définition suivante.
\end{recul}
La définition suivante apparaît pour la première fois dans
l'article~\cite{HartmanisS65} d'Hartmanis et Stearns.
\begin{definition}[classes de complexité en temps déterministe]\label{temps:def:dtime}%
  \begin{itemize}
  \item\index{DTIME@\dtime}%
    Pour une fonction $t:\nn\to\nn$, la classe $\dtime(t(n))$ est l'ensemble
    des langages reconnus par une machine de Turing $M$ telle qu'il existe une
    constante $\alpha$ pour laquelle, sur toute entrée $x$, $M(x)$ fonctionne
    en temps $\leq\alpha t(|x|)$.
  \item Si $\mathcal{T}$ est un ensemble de fonctions, alors
    $\dtime(\mathcal{T})$ désigne $\cup_{t\in\mathcal{T}}\dtime(t(n))$.
  \end{itemize}
\end{definition}
\begin{remarque}%
  Dans le domaine de la complexité (contrairement à la calculabilité), toutes
  les machines que nous considérerons s'arrêteront sur toute entrée. C'est par
  exemple implicite dans la définition précédente puisque $M(x)$ est censée
  fonctionner en temps $\leq\alpha t(|x|)$. La question n'est plus de savoir
  si une machine s'arrête, mais en combien de temps elle le fait.
\end{remarque}

\begin{remarque}%
  Pour résoudre la plupart des problèmes non triviaux, il faut lire la
  totalité de l'entrée $x$. Ainsi le temps de calcul mis par la machine est au
  moins $n=|x|$, et les classes $\dtime(t(n))$ ont peu d'intérêt pour
  $t(n)=o(n)$.
\end{remarque}
Avant de poursuivre, mentionnons quelques propriétés évidentes des classes
$\dtime(t(n))$.
\begin{proposition}%
  \begin{enumerate}
  \item Si pour tout $n$, $f(n)\leq g(n)$ alors
    $\dtime(f(n))\subseteq\dtime(g(n))$;
  \item pour tout $t(n)\geq n$, $\dtime(t(n))$ est clos par union finie,
    intersection finie et complémentaire.
  \end{enumerate}
\end{proposition}
\begin{preuve}%
  \begin{enumerate}
  \item Si $L\in\dtime(f(n))$ alors il existe une machine reconnaissant $L$ en
    temps au plus $\alpha f(n)$ donc a fortiori en temps majoré par $\alpha
    g(n)$, ce qui implique $L\in\dtime(g(n))$.
  \item Si $L_1,L_2\in\dtime(t(n))$, soit $M_1$ et $M_2$ deux machines
    reconnaissant $L_1$ et $L_2$ en temps $\leq\alpha_1 t(n)$ et $\leq\alpha_2
    t(n)$ respectivement. Alors une machine pour $L_1\cup L_2$ (resp. $L_1\cap
    L_2$) est la machine $M_\cup(x)$ (resp. $M_\cap(x)$) qui exécute $M_1(x)$
    puis $M_2(x)$ et accepte ssi l'une des deux accepte (resp. les deux
    acceptent). Puisque cette machine doit revenir au début du ruban de
    lecture entre les calculs de $M_1$ et de $M_2$, elle fonctionne en temps
    $\leq\alpha_1 t(n)+\alpha_2 t(n)+O(n)$. Puisque $t(n)\geq n$, on a donc
    $L_1\cup L_2\in\dtime(t(n))$ (resp. $L_1\cap L_2\in\dtime(t(n))$).

    Une machine pour $^cL_1$ est la machine $M_c(x)$ qui exécute $M_1(x)$ et
    accepte ssi $M_1(x)$ rejette : elle fonctionne en temps $\leq\alpha_1
    t(n)$ donc $^cL_1\in\dtime(t(n))$.\cqfd
  \end{enumerate}
\end{preuve}
Pourquoi définir la classe \dtime{} à une constante $\alpha$ près ? La raison
vient du résultat suivant qui montre que le fonctionnement d'une machine peut
être accéléré par n'importe quel facteur constant. En d'autres termes, le temps
de calcul d'une machine n'est une mesure pertinente qu'à une constante près.
\begin{recul}%
  Il n'y a pas de magie dans ce résultat : pour accélérer une machine, il
  suffit d'agrandir l'alphabet pour faire plus de calculs en une étape. C'est
  grosso-modo ce qu'on fait en remplaçant les micro-processeurs 32 bits par
  des micro-processeurs 64 bits.
\end{recul}
Comme on l'a vu, on ne peut pas descendre en dessous de $n$ pour le
temps d'exécution d'une machine raisonnable, ce qui explique la forme
$(1+\epsilon)n+\epsilon t(n)$ utilisée dans le théorème suivant. Si $n=
o(t(n))$ alors cela signifie réellement une accélération par n'importe quelle
constante. Ce résultat est dû encore à Hartmanis et
Stearns~\cite{HartmanisS65}.
\index{Accélération linéaire (théorème)!en temps}%
\begin{theoreme}[accélération linéaire]\label{temps:th:accel_lin}%
  Pour toute constante $\epsilon>0$, si un langage $L$ est reconnu par une
  machine $M$ fonctionnant en temps $\leq t(n)$, alors il existe une machine
  $M'$ reconnaissant $L$ et fonctionnant en temps $\leq (1+\epsilon)n+\epsilon
  t(n)$.
\end{theoreme}
\begin{ideepreuve}%
  L'astuce consiste à agrandir l'alphabet pour pouvoir réaliser en une seule
  fois plusieurs étapes de calcul de la machine de départ. Pour réaliser $c$
  étapes d'un coup, il faut connaître le voisinage de rayon $c$ autour de la
  cellule en cours : chaque nouvelle cellule contiendra des $(2c+1)$-uples
  d'anciennes cellules (ce qui revient à passer à l'alphabet de travail
  $\Gamma^{2c+1}$). En réalité nous n'allons pas simuler $c$ anciennes étapes en
  une seule nouvelle, mais en $6$ nouvelles : les informations nécessaires
  sont en effet contenues dans les voisines de gauche et de droite qu'il nous
  faut donc visiter (voir la figure~\ref{temps:fig:acceleration}).
\end{ideepreuve}

% ...
