\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}
\fancyhead[R]{\textsc{Langage formels, calculabilité et complexité}}
\fancyhead[L]{TD7} % except the center
\fancyfoot{} % except the center
\fancyfoot[L]{louis.jachiet@ens.fr}
\fancyfoot[C]{https://louis.jachiet.com/tps.html}
\fancyfoot[R]{30 novembre 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 ,
%  counter-within = section ,
%  counter-format = se.qu\IfQuestionSubtitleT{:} ,
%solution/print = true
}
\newtheorem{defi}{Definition}

\newcommand\myeq{\stackrel{\mathclap{\normalfont\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{TD7 : Langages formels, calculabilité et complexité}

\begin{document}
\pagestyle{fancy}

\section{Problèmes de factorisation}

On considère les trois problèmes suivants :

\begin{itemize}
\item \textsc{FindSmallestFactor} Étant donné $N\in\mathbb{N}^*$ renvoie le
  plus petit $k\in\mathbb{N}$ avec $k\geq 2$ tel que $k$ divise $N$.

\item \textsc{FindGreatestFactor} Étant donné $N\in\mathbb{N}^*$ renvoie le
  plus grand $k\in\mathbb{N}$ avec $k< N$ tel que $k$ divise $N$.

\item \textsc{HasFactor} Étant donné $(N,M)\in\mathbb{N}^*{}^2$ décide
  s'il existe un facteur non trivial de $N$ plus petit que $M$.
  
\end{itemize}

\begin{question}
Montrer que si l'on sait résoudre un de ces problèmes en temps
polynomial, alors on sait résoudre les trois. Attention le temps
polynomial se réfère à la taille de l'entrée qui est logarithmique en
les nombres représentés.
\end{question}

\begin{solution}
  Si l'on sait résoudre l'un des deux premiers alors on sait
  factoriser $N$ et donc répondre aux deux autres problèmes.

  Pour le dernier, on va montrer qu'on peut s'en servir pour résoudre
  le premier.  Il s'agit de travailler par dichotomie. On commence par
  $k_1=1$ et $k_2=N$ ensuite, tant que $k_1+1<k_2$ on choisit
  $M=\lfloor(k_1+k_2)/2 \rfloor$ et on regarde s'il existe un facteur
  de $N$ plus petit que $M$, si c'est le cas on pose $k_2=M$ sinon on
  pose $k_1=M$. Une fois que notre algorithme s'arrête, on a
  $k_1+1=k_2$ et donc $k_1+1$ est le plus petit nombre qui est un
  facteur non trivial de $N$. À chaque étape $k_1-k_2$ perd un bit on
  fait donc un nombre linéaire d'appels à \textsc{HasFactor}.
  
\end{solution}

\begin{question}
  Montrer que \textsc{HasFactor} est dans $\NP$. \emph{Vous pouvez
    supposer que tester la primalité d'un nombre est dans $\DP$.}
\end{question}

\begin{solution}
 Ce problème peut être traité en regardant le certificat $(p_1,e_1)
 \dots, (p_k,e_k)$ et en vérifiant que chacun des $p_i$ sont premiers,
 que $N=\prod_i p_i^{qe_i}$ et que le plus petit $p_i$ est bien plus
 petit que $M$.
\end{solution}

\begin{question}
  Montrer que \textsc{HasFactor} est dans $\coNP$.
\end{question}

\begin{solution}
De la même manière que pour $\NP$, on regarde les mêmes certificats,
comme ils donnent une décomposition parfaite, il suffit de vérifier
que le certificat est bien tel que chaque $p_i$ soit plus grand que
$M$.
\end{solution}

\section{Propriétés de clôture}

\begin{question}
Montrer que les langages décidables en temps polynomial sont stables
par intersection, union, complémentation et étoile (i.e. le langage $L^*$). 
\end{question}

\section{Fonctions à sens unique}

Supposons que :
\begin{itemize}

\item on a une bijection $f$ des entiers sur $n$ bits vers les entiers
  sur $n$ bits, pour tout $n$ (i.e., sur une entrée $x$ de $n$ bits,
  $f(x)$ est un entier sur $n$ bits tel que $f(x)=f(y) \Rightarrow
  x=y$).

\item la fonction $f$ se calcule en temps polynomial.

\item la fonction inverse de $f$ ne peut pas se calculer en temps
  polynomial. (On dit que c’est une fonction à sens unique.)
\end{itemize}

\begin{question}
  Montrer que si une telle bijection existe, alors  $\DP\neq \NP$.

  \hfill \emph{Suggestion~: Montrer que le langage $L = \{(x,f(y)) : x \leq y \}$
  appartient à  $\NP\setminus\DP$.}
\end{question}

\begin{solution}
$L$ est $\NP$ en considérant le certificat étant $x,y$.

Si $L$ est dans $\DP$ alors étant donné $x$ tel qu'il existe $y$ avec
$x=f(y)$ on cherche par dichotomie sur $z$ le plus petit $z$ tel que
$(z,f(y))$ est dans le langage $L$. On trouve alors la fonction
inverse de $f$ en temps polynomial ce qui était supposé impossible.
\end{solution}

\begin{question}
  Montrer de plus, que si elle existe, alors $\NP\cap \coNP\neq \DP$.
\end{question}

\begin{solution}
On fonctionne de la même manière, il suffit d'exhiber un $y$ qui nous
donne le contre-exemple. Et par dichotomie sur le langage
complémentaire de $L$ on peut aussi inverser $f$ en un nombre linéaire d'appels à $\bar{L}$.
\end{solution}


\section{Quines}


Pour deux MT $A$ et $B$ on note $A\cdot B$ une MT qui exécute $B$
après avoir exécuté $A$.

Pour chaque mot $w\in\Sigma^*$, soit $P(w)$ un MT sur $\Sigma$ qui
écrit le mot $w$ sur le ruban.

\begin{question}
  Expliquer pourquoi la fonction $q: \mathbb{N} \rightarrow \mathbb{N}$ est récursive (i.e. calculable).

  $$ q(n) =
  \begin{cases}
    \code{P(w)} & \mbox{s'il existe } w\in\Sigma^* \mbox{ tel que } n=\code{w} \\
    \bot & \mbox{sinon} \\
  \end{cases} $$
\end{question}

\begin{solution}
  $q(n)$ peut être calculé en calculant le $w$ tel que $n=\code{w}$
  s'il existe puis affiche $\code{P(w)}$. Le calcul de $w$ est récursif
  par la forme du codage tandis que $P(w)$ est aussi calculable car il
  suffit de mettre $|w|$ états, l'état $i$ affichant $w_i$ puis
  calculer le code de $\code{P(w)}$.
\end{solution}

\begin{question}
  Expliquer pourquoi la fonction $s_2(m,n) : \mathbb{N}^2 \rightarrow \mathbb{N}$ est récursive.
  $$ s_2(m,n) =
  \begin{cases}
    \code{A\cdot B} & \mbox{s'il existe } A,B \mbox{ telles que } \code{A}=m \land \code{B}=n\\
    \bot & \mbox{sinon}
  \end{cases}
  $$
\end{question}

\begin{solution}
  Étant les codes $\code{A}$ et $\code{B}$ on retrouve $A$ et $B$ puis
  on concatène les deux calculs.

\end{solution}

\begin{question}
  En déduire qu'il existe une MT $M$ qui termine en affichant $\code{M}$ sur la bande.
\end{question}

\begin{solution}

  Soit $s$ qui calcule $x\rightarrow s_2(x,q(\code{x}))$ on regarde
  $M$ la MT qui calcule $s\cdot P({\code{s}})$ donc $\code{M}=\code{s\cdot P({\code{s}})}$
  
  Une exécution de $M$ donne sur le ruban : $s\cdot
  P({\code{s}}) \rightarrow s(P({\code{s}})) \rightarrow
  s(\code{s})=s_2(\code{s},q(\code{\code{s}})) \rightarrow
  \code{s\cdot P({\code{s}})}=\code{M}$.  
\end{solution}


\end{document}

