\documentclass{scrartcl}
\usepackage[margin=1in, left=0.5in, right=0.5in]{geometry}
\usepackage[utf8]{inputenc}
\usepackage[francais]{babel}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{fancyhdr}
\usepackage{mathtools}
\usepackage{graphicx}
\usepackage{subcaption}
\fancyhead[R]{\textsc{Langage formels, calculabilité et complexité}}
\fancyhead[L]{TD9} % except the center
\fancyfoot{} % except the center
\fancyfoot[L]{louis.jachiet@ens.fr}
\fancyfoot[C]{https://louis.jachiet.com/tps.html}
\fancyfoot[R]{14 décembre 2017}
\newcommand{\DP}{\mathcal{P}}
\newcommand{\NP}{\mathcal{NP}}
\newcommand{\coNP}{\mbox{co-}\mathcal{NP}}
\newcommand{\B}{\mathcal{B}}
\newcommand{\X}{\mathcal{X}}
\newcommand{\I}{\mathcal{I}}
\newcommand{\F}{\mathcal{F}}
\newcommand{\R}{\mathcal{R}}
\newcommand{\Ls}{{\mathcal{L}_\Sigma}}
\newcommand{\Lc}{{\mathcal{L}}}
\newcommand{\ml}{\mu_{\mathcal{L}}}
\newcommand{\Mn}{M_n(\Ls)}
\newcommand{\Vn}{{M_{n,1}(\Ls)}}
\newcommand{\tr}[1]{\xrightarrow{#1}}
\newcommand{\td}{\tilde{\delta}}
\newcommand{\norm}[1]{\left\lvert#1\right\rvert}
\newcommand{\code}[1]{{\langle}{#1}{\rangle}}
\renewcommand{\headrulewidth}{0.4pt}
\renewcommand{\footrulewidth}{0.4pt}
\usepackage{exsheets}[2014/09/14] % v0.16 or newer
\SetupExSheets{
  headings = runin ,
  headings-format = \large\bfseries\sffamily ,
  subtitle-format = \large\bfseries\sffamily ,
  question/type = exam,
  %  counter-within = section ,
%  counter-format = se.qu\IfQuestionSubtitleT{:} ,
%solution/print = true
}
\newtheorem{defi}{Définition}
\setlength{\parindent}{0pt}
\newcommand\myeq{\stackrel{\mathclap{\codealfont\mbox{def}}}{=}}

\newcommand*\fo[1]{\tikz[baseline=(char.base)]{
                \node[shape=circle,draw,inner sep=2pt] (char) {#1};}}
\usepackage{tikz}
\usetikzlibrary{automata,positioning,trees}

\author{}
%\date{}
\title{TD9 : Langages formels, calculabilité et complexité}

\begin{document}
\pagestyle{fancy}

\section{Réduction de CNF-SAT à chemin hamiltonien}

Un chemin de $s$ à $t$ dans un graphe $G$ est dit hamiltonien si le
chemin passe exactement une fois dans chaque nœud du graphe.  On
définit alors le problème $HAMPATH$ de la façon suivante :
$$HAMPATH = \{ (G,s,t) \mid \mbox{il existe un chemin hamiltonien de } s \mbox{ à } t \mbox{ dans le graphe orienté } G\}$$

\begin{question}
  Montrer que $HAMPATH$ est $\NP$-complet.
\end{question}

\begin{solution}

Considérons le graphe avec $3l+2$ nœuds par variable $i$ ($v^i_0 \dots
v^i_{3k}$) et $s_i$. On relit bilatéralement les $v^i_j$ à $v^i_{j-1}$
et $v^i_{j+1}$ quand ils existent. On ajoute $s_i\rightarrow v^i_0$,
$v^i_0\rightarrow s_{i+1}$, $s_i\rightarrow v_{3k}$ et
$v_{3k}\rightarrow s_{i+1}$. Pour chaque clause $j$ on ajoute un nœud
$C_j$ et on branche pour chaque $x_i$ de la clause les arcs
$v^i_{3j+1}\rightarrow C_j$ et $C_j \rightarrow v^i_{3j+2}$ tandis que
pour chaque $\bar{x}_i$ dans $C_j$ on ajoute $v^i_{3j+2}\rightarrow
C_j$ et $v^i_{3j+1}\rightarrow C_j$. La réduction polynomiale consiste
maintenant à chercher un chemin hamiltonien de $s_1$ à $s_{k+1}$.

Soit un chemin hamiltonien de $s_1$ à $s_{k+1}$.  Nous allons montrer par
induction sur $i$ puis $j$ que les nœuds $v^i_j$ apparaissent dans le
chemin par $i$ croissant et que pour un $i$ donné les $v^i_j$
apparaissent par $j$ monotone (soit croissant soit décroissant) et que
premier nœud visité après la couche $i$ est $s_{i+1}$.

Supposons la propriété vraie pour tout $j<i$ avec $i\in \mathbb{N}^*$
(trivialement vraie pour $i=0$ puisque $s_1$ est le départ du chemin).
$s_i$ n'est suivie que de $v^i_0$ et $v^i_{3k}$. Les deux cas sont
symétriques (mais l'un implique de traiter la couche par $j$ croissant
l'autre décroissant). Supposons $s_i$ est suivi de $v^i_0$. Le nœud
suivant de $v^i_0$ ne peut pas être $s_{i+1}$ car $v^i_1$ n'est relié
qu'à deux nœuds dont $v^i_0$.
Donc le nœud suivant $v^i_0$ est $v^i_1$. Montrons maintenant la
propriété de croissance par induction sur $j$:
\begin{itemize}
  \item Elle est vraie pour
    $j=1$.
  \item Soit $1\leq j < 3k$ et supposons la propriété vraie pour
    $j$. Si $j$ est un multiple de $3$ alors comme $v^i_j$ n'est
    reliée qu'à $v^i_{j+1}$ et $v^i_{j-1}$ (qui est visité par
    induction) le successeur de $v^i_j$ ne peut être que $v^i_{j+1}$
    et donc la propriété est vérifiée pour $j+1$.
  \item Si $j=3n+1$ alors $v^i_{j}$ ne peut être suivi que de $C_n$ et
    de $v^i_{j+1}$ (par induction $v^i_{j-1}$ est déjà visité). Si le
    nœud suivant est $v^i_{j+1}$ la propriété est obtenue. Sinon nous
    avons dans le chemin $v^i_{3n+1} \rightarrow C_n$. Si le nœud
    suivant $C_n$ n'est pas $v^i_{j+1}$ alors $v^i_{3n+2}$ ne sera
    plus relié qu'à un unique nœud non visité $v^i_{3n+3}$ et donc ne
    pourra pas être pris par un chemin hamiltonien. Donc le nœud
    suivant $C_n$ est forcément $v^i_{j+1}$.

  \item Si $j=3n+2$ alors les successeurs possibles de $v^i_j$ sont
    $v^i_{j+1}$ (auquel cas la propriété est claire) et $C_n$ (quand
    $\bar{x}_i$ apparaît dans $C_n$). Dans le cas où $v^i_j$ est suivi
    de $C_n$ alors $v^i_{j+1}$ n'est plus relié qu'à un unique nœud et
    donc le chemin hamiltonien ne pourra plus être construit, donc
    $v^i_j$ ne peut être suivi que de $v^i_{j+1}$.
\end{itemize}

Dans le cas où $v^i_{3k}$ est le successeur de $s_i$ alors on prouve
la même chose dans l'autre sens, les nœuds $v^i_j$ peuvent suivis que
de $v^i_{j-1}$ sauf dans le cas où $j=3n+2$ auquel cas on peut avoir
$v^i_j\rightarrow C_{\lfloor j/3\rfloor}\rightarrow v^i_{j-1}$ (dans
le cas $j=3n+1$ ce n'est pas possible car $v^i_{j-1}$ ne serait plus
relié qu'à un unique nœud).

Dans tous les cas les $v^i_j$ sont parcourus en $j$ monotone et en
arrivant au bout le seul successeur possible est $s_{i+1}$.

Nous voulons montrer que si l'on a un chemin hamiltonien alors nous
avons une solution à la formule CNF. Pour cela on fixe $x_i=\top$ ssi
les $v^i_j$ sont parcourus en ordre croissant. Par la façon dont nous
avons encodé les clauses, comme tous les nœuds $C_j$ sont visités nous
avons $v^i_{3j+1}\rightarrow C_j\rightarrow v^i_{3j+2}$ quand
$x_i=\top$ et $x_i$ apparaît dans $C_j$ et inversement
$v^i_{3j+2}\rightarrow C_j\rightarrow v^i_{3j+1}$ quand $x_i=\bot$ et
$\bar{x}_i$ apparaît dans $C_j$. Donc la formule est bien satisfaite
par l'assignement donné.

Montrons maintenant que si l'on a un assignement alors il existe une
solution au chemin hamiltonien. Pour cela, on choisit pour chaque
clause un de ses représentants qui la satisfait et le chemin est de
parcourir chaque couche dans l'ordre croissant quand $x_i=\top$ et
décroissant quand $x_i=\bot$. Si $x_i$ est le littéral qui satisfait
$C_j$ alors on prend le chemin $v^i_{3j+1}\rightarrow C_j\rightarrow
v^i_{3j+2}$ sinon $v^i_{3j+1}\rightarrow v^i_{3j+2}$. Dans le cas où
$\bar{x}_i$ satisfait $C_j$ alors on prend le chemin
$v^i_{3j+2}\rightarrow C_j\rightarrow v^i_{3j+1}$ sinon
$v^i_{3j+2}\rightarrow v^i_{3j+1}$. On voit que tous les $v^i_j$, les
$s_i$ aussi et les $C_j$ sont visités une unique fois.
\end{solution}

\emph{Suggestion : partir d'une formule CNF-SAT à $k$ clauses
  $(C_1,\dots,C_k)$ et $l$ variables $(x_1,\dots, x_l)$ et construire
  un graphe qui contient (pour $i$ une variable et $j$ une clause) :
  trois nœuds $x_i^j$, $\bar{x}_i^j$ et $n^i_j$ ; deux nœuds $s_i$ et
  $n^0_i$ ; un nœud $C_j$ plus un nœud $s_{l+1}$ et utilise les
  gadgets suivants :}
\begin{figure}[h]
\begin{subfigure}{0.6\textwidth}
\begin{center}
\begin{tikzpicture}[shorten >=1pt,scale=0.6, every node/.style={scale=0.6},node distance=1cm,on grid,auto]
    \node[state] (X1)   {$n^0_i$};
    \node[state] (X2) [right=of X1] {$x^1_i$};
    \node[state] (X3) [right=of X2] {$\bar{x_i}^1$};
    \node[state] (X4) [right=of X3] {$n_i^1$};
    \node (X5) [right=of X4] {$\dots$};
    \node (X5b) [right=of X5] {$\dots$};
    \node[state] (X6) [right=of X5b] {$x_i^k$};
    \node[state] (X7) [right=of X6] {$\bar{x_i}^k$};
    \node[state] (X8) [right=of X7] {$n_i^k$};
    \node[state] (S1) [above right=3cm and 0cm of X5]   {$s_i$};
    \node[state] (T1)  [below right=3cm and 0cm of X5]  {$s_{i+1}$};
    \path[->]
    (S1) edge [bend right] (X1)
    (S1) edge [bend left] (X8)
    (X1) edge [bend right] (T1)
    (X8) edge [bend left] (T1)
    (X2) edge [bend left] (X1) 
    (X1) edge [bend left] (X2) 
    (X2) edge [bend left] (X3) 
    (X3) edge [bend left] (X2) 
    (X3) edge [bend left] (X4) 
    (X4) edge [bend left] (X3) 
    (X5) edge [bend left] (X4) 
    (X4) edge [bend left] (X5) 
    (X5b) edge [bend left] (X6) 
    (X6) edge [bend left] (X5b)
    (X6) edge [bend left] (X7) 
    (X7) edge [bend left] (X6)
    (X8) edge [bend left] (X7) 
    (X7) edge [bend left] (X8)  ;
\end{tikzpicture}
\caption{Gadget de variable}
\label{fig:color}
\end{center}
\end{subfigure}
\begin{subfigure}{0.3\textwidth}
\begin{subfigure}{\textwidth}
\begin{center}
\begin{tikzpicture}[shorten >=1pt,scale=0.6, every node/.style={scale=0.6},node distance=1cm,on grid,auto]
    \node[state] (X2) [right=of X1] {$x^j_i$};
    \node[state] (X3) [right=of X2] {$\bar{x_i}^j$};
    \node[state] (C) [below right=1cm and 0.5cm of X2] {$C_j$};
    \path[->]
    (X2) edge (C)
    (C) edge (X3)
    (X2) edge [bend left] (X3) 
    (X3) edge [bend left] (X2) ;
\end{tikzpicture}
\caption{Gadget pour $x_i$ utilisé dans $C_j$ }
\label{fig:color}
\end{center}
\end{subfigure}
\begin{subfigure}{\textwidth}
\vspace{3em}
\begin{center}
\begin{tikzpicture}[shorten >=1pt,scale=0.6, every node/.style={scale=0.6},node distance=1cm,on grid,auto]
    \node[state] (X2) [right=of X1] {$x^j_i$};
    \node[state] (X3) [right=of X2] {$\bar{x_i}^j$};
    \node[state] (C) [below right=1cm and 0.5cm of X2] {$C_j$};
    \path[->]
    (X3) edge (C)
    (C) edge (X2)
    (X2) edge [bend left] (X3) 
    (X3) edge [bend left] (X2) ;
\end{tikzpicture}
\caption{Gadget pour $\bar{x}_i$ utilisé dans $C_j$ }
\label{fig:color}
\end{center}
\end{subfigure}
\end{subfigure}
\end{figure}

\begin{question}
  Montrer que le problème du chemin hamiltonien reste $\NP$-complet
  pour les graphes non orientés.
\end{question}

\begin{solution}
Étant donné une instance du problème du chemin hamiltonien sur le
graphe $G=(V,E)$ on triple chaque nœud $n$ en $n_{in}$, $n_{out}$ et
$n_{mid}$. Pour chaque nœud on ajoute $n_{in}\rightarrow
n_{mid}\rightarrow n_{out}$ et chaque arc $(u,v)$ est transformé en
$u_{out}\rightarrow v_{in}$. Enfin on enlève les nœuds $s_{in}$,
$s_{mid}$, $t_{out}$ et $t_{mid}$.

Chaque chemin dans $G$ de $s$ à $t$ est clairement transposable en un
chemin dans $G'$ de $s_{out}$ à $t_{in}$.

Soit un chemin $n_1,\dots n_l$ de $G'$ de $s_{out}$ à $t_{in}$. Nous
allons montrer que le chemin $n_1, \dots, n_k$ est une succession de
nœuds $n_{in}$, $n_{mid}$, $n_{out}$ (le $in$, $mid$, $out$ du même
nœud) où $n_{out}$ précède $n'_{in}$ quand $n\rightarrow n'$ dans par
induction sur $k$ sauf le premier qui vaut $s_{out}$ et le dernier qui
vaut $t_{in}$.

Pour $k=1$, on a $n_1=s_{out}$ donc c'est clair .

Pour $k<l$ si on suppose que $v_1, \dots v_k$ est une alternance $in$,
$mid$, $out$, alors si on a $v_k=n_mid$ c'est que l'on vient de
$n_{in}$ et que le seul nœud suivant est $n_{out}$. Si $v_k=n_in$
alors le noeud $n_{mid}$ n'est pas encore visité (car la seule manière
de rentrer dans $n_{mid}$ c'est par $n_{in}$ ou $n_{out}$) et doit
l'être immédiatement sinon il ne sera plus relié qu'à un nœud non
visité ($n_{out}$). Si $v_k=v_{out}$ alors $n_{in}$ et $n_{mid}$ ont
été visités et $n_{out}$ n'est relié qu'à des nœuds $n'_{in}$ tels que
$n'$ suit $n$ dans $G$.

Au bout du compte, un chemin hamiltonien dans $G'$ a la forme
$s_{out}, n^1_{in}, n^1_{mid}, n^1_{out}, \dots , n^k_{in}, n^k_{mid},
n^k_{out},t_{in}$ et donc l'on peut retrouver un chemin dans le graphe
original $s, n^1, \dots, n^k,t$.
\end{solution}

\section{Le théorème de hiérarchie temporelle}

Pour simplifier la programmation des machines, nous n'utiliserons ici
que des machines de Turing déterministes à 2 bandes. On utilise un
encodage raisonnable des MT que l'on note $\code{M}$ pour une machine
$M$.  Par exemple, $\code{M}$ code les états par des mots de
$\{0,1\}^*$, l'alphabet commun des rubans par des mots de
$\{\alpha,\beta\}^*$, une direction de changement des têtes par
$\{<,>,\_\}^2$. Une machine est alors représentée par une suite de
transitions pour chaque état. Pour l'état $e$ on représente ça de la
façon $e|a_1,b_1,c_1,d_1,e_1,f_1,\dots a_k,b_k,c_k,d_k,e_k,f_k|$ où
les $e, (e_i)_i$ sont des états, les $(a_i)_i,(b_i)_i,(c_i)_i,(d_i)_i$
sont des lettres du ruban, les $(f_i)_i$ des directions. $a$
correspond à la lettre lue sur le premier ruban, $b$ sur le second
ruban, $c$ à celle écrite sur le premier ruban et $d$ à celle sur le second.

\begin{defi}
  L'ensemble $TIME(f(n))$ correspond à l'ensemble des problèmes pour
  lesquels il existe une machine de Turing déterministe qui décide en
  moins de $f(n)$ étapes de calcul les entrées de taille $n$.
\end{defi}

{Attention, de la même manière qu'on dit que le tri peut se faire en
  $O(n\times ln(n))$ en omettant de dire ``sur une entrée de taille
  $n$'', on écrit toujours $TIME(f(n))$ mais il faut bien évidemment
  lire $TIME(n\rightarrow f(n))$ car le $n$ représente la taille de
  l'entrée.}

{Dans la suite de ce TD, si besoin, vous pouvez vous reposer sur le
  théorème d'accélération linéaire qui énonce que pour tout $g$ et
  tout $\epsilon > 0$ \textbf{fixés}, $TIME(g(n))\subseteq
  TIME(n+2+\epsilon g(n))$.}

\begin{defi}
  Une fonction $f$ est dite \emph{constructible en temps} s'il existe
  une machine $M$ qui prend en entrée un mot $1^n$ et produit la
  représentation binaire de $f(n)$ en temps $f(n)$. 
\end{defi}


Le théorème de hiérarchie temporelle dit que si $f$ est une fonction
constructible en temps alors : $$TIME\left(o\left(\dfrac{f(n)}{log f(n)}\right)\right)\subsetneq TIME(f(n))$$

\emph{Nous allons ici montrer une version amoindrie,
  $TIME(f(n))\subsetneq TIME(f(2n+1)^3)$ avec $n^3\leq f(n)$.}

Pour $f$ constructible en temps, on définit le langage
$Halt_f = \{\code{M}\#x \mid M \mbox{ accepte } x \mbox{ en } f(|x|) \mbox{  étapes}\}$.


\begin{question}
  Justifier que $Halt_f\in TIME(f(n)^3)$.
\end{question}

\begin{solution}
  Nous allons simuler une machine $M$ en temps $f(n)^3$. Au départ le
  ruban 1 contient $\code{M}\#x$. Notre pseudo code est:

  \begin{tabular}{l|c|r}
    Action & État de bande 1 & État de bande 2 \\\hline
    Départ & $\code{M}\#x$ \\
    Calculer $f(n)$ & $\code{M}\#x_1 \dots x_k\#f(n)$ \\
    Mettre $x$ dans $2$ & $\code{M}\#f(n)$ & $x_1 0 x_2 0 \dots x_k 0$ \\
    Mettre état de départ et les têtes dans la bande 1 & $\code{M}\#f(n)\#e_0,x_1,0$ & $t_1t_2x_2 0 \dots x_k 0$\\
    Répéter & $\code{M}\#k\#e,a,b$ & $w$ \\
    Copier $e,a,b$ à la fin de $w$ &  $\code{M}\#k\#e,a,b$ & $w\#e,a,b$ \\
    Trouver la transition correspond à $e,a,b$ dans $\code{M}$ \\
    Stocker $f$  correspond dans les états de la MT & & \\
    Écrire le $e$ de la transition sur la bande 2  &  $\code{M}\#k\#e,a,b$ & $w\#e',a,b$ \\
    Écrire le $e$ de la transition depuis la bande 2 sur 1  &  $\code{M}\#k\#e',a,b$ & $w\#e',a,b$ \\
    \\
    Trouver $t_1$ sur la bande 2  && \\
    Échange $t_1$ et $a$ puis\\
    déplacer la tête et mettre ce qu'on lit à la place de $a$ & $\code{M}\#k\#e',a',b$ & \\
    Trouver $t_2$ sur la bande 2  && \\
    Échange $t_2$ et $b$ puis\\
    déplacer la tête et mettre ce qu'on lit à la place de $b$ & $\code{M}\#k\#e',a',b'$ & \\
    \\
    Décrémenter $k$\\
    Si $k=0$ on termine et accepte ssi $e$ est acceptant dans $\code{M}$ \\ 
    
  \end{tabular}
\end{solution}

 Supposons par l'absurde que $Halt_f\in TIME\left(\dfrac{f(\lfloor n/2
   \rfloor)}{2}\right)$. Soit $K$ décidant $Halt_f$ en temps
 $f(\lfloor n/2 \rfloor)/2$ , on peut alors construire $D_K$ qui prend
 en entrée $\code{M}$ le code d'une machine de Turing et lance $K$ sur
 $\code{M}\#\code{M}$. $D_K$ accepte quand $K$ refuse et refuse quand
 $K$ accepte.

\begin{question}
  Justifier que $D_K$ peut être construit de façon à ce que $D_K \in TIME(f(n))$.
\end{question}

\begin{solution}
Pour $D_K$ il faut lire $\code{M}$ puis l'écrire sur la bande 2,
revenir au début de la bande 2, ajouter $\#$ sur la bande 1 et copier
le contenu de $2$ sur $1$ puis remettre les têtes au début.
Ensuite on lance $K$ et on inverse le résultat.

Le temps de calcul est celui de $K$ puis une action linéaire donc
$O(n+f(\rfloor 2n+1 \lfloor))$ où $n=\norm{\code{M}}$. Par le théorème
on a bien ce que l'on veut.

\end{solution}

\begin{question}
Justifier que $D_K$ ne peut pas exister par un argument de diagonalisation.
\end{question}

\begin{solution}
L'acceptation de $D_K$ lancée sur $\code{D_K}$ est l'inverse de celle
de $K$ sur $\code{D_K}\#\code{D_K}$ qui est la même que celle de $D_K$
sur $\code{D_K}$ (car $D_K\in TIME(f(n))$). Mais donc $D_K$ s'accepte
si et seulement si elle se refuse. Donc $D_K$ ne peut pas exister.
\end{solution}

\begin{question}
En déduire que $TIME(f(\lfloor n/2 \rfloor)/2)\subsetneq TIME(f(n)^3)$.
\end{question}

\begin{solution}
$D_K$ ne pouvant pas exister c'est donc que $Halt_f\not\in TIME(f(\lfloor n/2 \rfloor)/2)$.
\end{solution}

\begin{question}
  En déduire que $P\subsetneq EXPTIME \subsetneq 2-EXPTIME$.

  \emph{On rappelle : $P=\bigcup_{k\in\mathbb{N}} TIME(n^k)$, $EXPTIME=\bigcup_{k\in\mathbb{N}} TIME(2^{n^k})$, $2-EXPTIME=\bigcup_{k\in\mathbb{N}} TIME(2^{2^{n^k}})$ }
\end{question}

\begin{solution}
 $x\rightarrow 2^x$ est constructible en temps car on lit $1^n$ et on
  écrit $1^n\#0$ et ensuite on répète (la bande est $1^n\#^kx$) aller
  avant la partie $\#^k$ et si c'est un $1$ alors doubler $x$ sinon
  s'arrêter.
  
  Soit $f(x)=2^x$ on a $Halt_f$ qui est dans $EXPTIME$ mais pas dans
  $TIME(2^{x/2})$ donc pas dans $P$. De même avec $f(x)=2^{2^x}$ on a
  $EXPTIME$ strictement inclus dans $2-EXPTIME$.
\end{solution}

\section{Un problème $EXPTIME$ complet}

\begin{question}
Justifier que $f(x)=2^x$ est constructible en temps. En déduire que $Halt_f\in EXPTIME$. 
\end{question}

\begin{solution}
  Voir plus haut.
\end{solution}

\begin{question}
  Soit $L\in EXPTIME$, donner une réduction polynomiale de $L$ à
  $Halt_f$. En déduire que $Halt_f$ est $EXPTIME$ complet.
\end{question}

\begin{solution}
Si $L\in EXPTIME$ on a $M$ et $k$ tel que $L$ est reconnu par $M$ en
temps $2^{n^k}$ donc étant donné un $x$ on lance notre machine pour
$Halt_f$ sur $\code{M}\#x\#1^{n^k}$.
\end{solution}

\section{Un problème $PSPACE$ complet}

L'ensemble des formules booléennes quantifiées (QBF) est défini par
induction :
\begin{itemize}
  
\item Une variable propositionnelle est une formule booléenne
  quantifiée ;
  
\item Si $\phi$ est une formule booléenne quantifiée, alors $\lnot
  \phi$ est une formule booléenne quantifiée ;
  
\item Si $\phi$ et $\psi$ sont deux formules booléennes quantifiées,
  alors $\phi \land \psi$ est une formule booléenne quantifiée ;
  
\item Si $\phi$ est une formule booléenne quantifiée et $p$ est une
  variable propositionnelle, alors $\forall p\phi$ et $\exists p\phi$
  sont des formules booléennes quantifiées.
\end{itemize}

Les QBF sont dotées de leur valeurs de vérité usuelle. Le langage
$TQBF$ est le langage des QBF valant vrai.

\begin{question}
  Montrer que le problème $TBQF$ est $PSPACE$ complet.
\end{question}

Suggestion pour la partie $PSPACE$ difficile : partir d'un problème
$L$ qui est $PSPACE$. Montrer que $L$ est décidé par une machine $K$
pour laquelle il existe $P\in \mathbb{N}[X]$ tel que sur une entrée de
taille $n$, $K$ accepte ou refuse en temps $2^{P(n)}$ avec $P(n)$ de
mémoire.  Faire une réduction de $L$ à $TQBF$ Encoder l'état de $K$ et
de la mémoire de $K$ avec un $P(n)$ uplet de $\{0,1\}$ et donner la
formule $\Phi(c_1,c_2, t)$ qui décrit si l'on peut passer de l'état
$c_1$ à $c_2$ en temps $2^t$ (utiliser une exponentiation rapide).

\begin{solution}
  Tester toutes les assignations met clairement le problème dans
  $PSPACE$ puisque qu'assignation a une taille linéaire et tester la
  formule peut alors se faire linéairement.

  Maintenant on réduit n'importe quel problème reconnu par une machine
  $M$ en espace $n^k$ et temps $2^{n^k}$ en simulant $M$ avec une
  formule.  Nous supposons que $M$ travaille sur un alphabet $\{0,1\}$
  donc la machine $M$ peut s'encoder avec $|M|$ variable pour
  déterminer l'état courant, $n^k$ variable pour savoir où est la tête
  et $n^k$ variable pour savoir le contenu de chaque case du ruban.

  Déterminer si l'on peut passer d'un état (du ruban et de la machine)
  $c_1$ à un état $c_2$ (tous deux étant des $2n^k+|M|$-uplets de
  variables) se fait en une formule $\Psi(c_1,c_2)$. Maintenant pour
  savoir si l'on peut passer de $c_1$ à $c_2$ en $2^t$ étapes on
  calcule $\Phi(c_1,c_2,t)$ avec $\Phi(c_1,c_2,0)=\Psi(c_1,c_2)$ et
$$\Phi(c_1,c_2,t+1) =
  \exists m \forall (c_3,c_4)
  (
         (c_3\neq c_1 \lor c_4 \neq m)
  \land (c_4\neq c_3 \lor c_3 \neq m)
  )
  \lor \Phi(c_3,c_3,t)$$

  Les $c_3,c_4$ sont ici des $2n^k+|M|$-uplets de variables. L'inégalité
  entre deux $l$-uplets $v_1,\dots v_l$ et $w_1, \dots, w_l$ est
  réalisée par la formule: $(v_1 \land \lnot w_1)\lor (\lnot v_1 \land w_1) \lor \dots \lor (v_l \land \lnot w_l)\lor (\lnot v_l \land w_l)$.
  
\end{solution}

\end{document}

