\documentclass[11pt,a4paper]{article}
\usepackage{french}

\begin{document}
	
\ \\
\large Ecole Normale Sup\'{e}rieure de Lyon\\
MIM1
\hfill Mardi 16 Mai 2000

\vspace {2cm} 
\begin{center}
Mod\`{e}les de Calcul et Complexit\'{e}
\end{center}
\normalsize 
\vspace {1cm} 
\begin{center}
I -
\end{center}
Une classe $\cal C$ de complexit\'{e} est dite effectivement 
\'{e}num\'{e}rable s'il existe une \'{e}num\'{e}ration effective de 
machines de Turing $(T_{i})_{i \geq 1}$ telles que ${\cal C} = \{L / $ 
il existe $i $ tel que $ L = L(T_{i})$.
\begin{enumerate} 
\item D\'{e}montrer que si $t$ est une fonction constructible en temps, 
$TIME(t(n))$ est effectivement \'{e}num\'{e}rable. 
\item D\'{e}montrer que pour toute fonction totale calculable $f$, il 
existe une fonction constructible en temps $t$ telle que $t(n) > f(n)$ 
pour tout entier naturel $n$. 
\end{enumerate} 

\begin{center}
II -
\end{center}
\begin{enumerate}
	\item Existe-t-il des candidats \`{a} \^{e}tre dans $NP - (P \cup 
	NPc)$ ?
	\item Dans cette partie, on consid\`{e}re eux classes de complexit\'{e} 
${\cal C}_{1}$ et ${\cal C}_{2}$ qui ont les propri\'{e}t\'{e}s 
suivantes :
\begin{itemize}
\item ${\cal C}_{1}$ et ${\cal C}_{2}$ sont effectivement 
\'{e}num\'{e}rables,
\item ${\cal C}_{1}$ et ${\cal C}_{2}$ est sont closes par variations 
finies, c'est-\`{a}-dire que si $A$ est un langage fini, $L \cup A \in 
{\cal C}_{i}$ \'{e}quivaut \`{a} $L \in {\cal C}_{i}$  (pour $i = 1, 
2$),
\item il existe des langages r\'{e}cursifs $L_{1}$ et $L_{2}$ tels 
que $L_{1} \not \in {\cal C}_{1}$ et $L_{2} \not \in {\cal C}_{2}$. 
\end{itemize}
Soient $(T_{j}^{i})_{j \geq 1}$, $i = 1, 2$, des \'{e}num\'{e}rations qui 
t\'{e}mignent de ce que les classes ${\cal C}_{i}$ sont effectivement 
\'{e}num\'{e}rables. On d\'{e}signe par $L_{j}^{i}$ le langage 
d\'{e}cid\'{e} par $T_{j}^{i}$.
\begin{enumerate}
	\item Soit $n$ un entier naturel. On d\'{e}signe par $z_{1}^{i, n}$ 
	le plus petit mot $z$ tel que $|z| \geq n$ et $z \in L_{1} \Delta 
	L_{1}^{i}$ et par $z_{2}^{i, n}$ le plus petit mot $z$ tel que 
	$|z| \geq n$ et $z \in L_{2} \Delta L_{2}^{i}$.
	
	On pose $r_{1}(n) = max_{i \leq n}\{|z_{1}^{i, n}|\} + 1$ et 
	$r_{2}(n) = max_{i \leq n}\{|z_{2}^{i, n}|\} + 1$. Prouver que les 
	fonctions $r_{1}$ et $r_{2}$ ainsi d\'{e}finies sont totales et 
	calculables.
	\item Soit $G$ le langage $\{u / r^{2n} \leq |u|  < r^{2n+1} $ et $ 
	n \geq 0 \}$, o\`{u} $r$ est une fonction constructible en temps 
	telle que $r(n) \geq max(r_{1}(n),  r_{2}(n))$.
	\begin{enumerate}
		\item Justifier l'existence d'une telle fonction $r$.
		\item D\'{e}montrer que $G$ est dans $P$.
		\item D\'{e}montrer que le langage $L = (G \cap L_{1}) \cup (\overline G \cap 
		L_{2})$ n'appartient ni \`{a} ${\cal C}_{1}$ ni \`{a}  ${\cal 
		C}_{2}$,  
		et que $L \geq_{P} L_{1} \oplus L_{2}$ o\`{u} $L_{1} \oplus L_{2}$ 
		est le langage $\{u / u = 1v $ et $ v \in L_{1}$ ou $ u = 0v $ et $ v 
		\in L_{2}\}$.
	\end{enumerate}	
\end{enumerate}
\item En d\'{e}duire que si $P \not = NP$ alors il existe un langage 
de $NP - P$ qui n'est pas $NP$-complet. 
\end{enumerate}
\end{document}
