\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{Factorization problems}

Let us consider the three following problems:

\begin{itemize}
\item \textsc{FindSmallestFactor} given $N\in\mathbb{N}^*$ find the
  smallest $k\in\mathbb{N}$ with $k\geq 2$ such that $k$ divide $N$.

\item \textsc{FindGreatestFactor} given $N\in\mathbb{N}^*$ find the
  biggest $k\in\mathbb{N}$ with $k< N$ such that $k$ divide $N$.

\item \textsc{HasFactor} given $(N,M)\in\mathbb{N}^*{}^2$ decide
  whether there exists a non-trivial factor of $N$ smaller than $M$.
  
\end{itemize}

\begin{question}
Show that, if you can solve any of these problems in polynomial time,
then you can solve all of these problems in polynomial time. Beware
that the time is considered in the size of the input which is
logarithmic in the considered numbers.
\end{question}

\begin{question}
  Show that these problems are $\NP$. \emph{You can assume that the
    primality test is $\DP$.}
\end{question}

\begin{question}
Show that these problems are $\coNP$.
\end{question}

\section{Closure properties}

\begin{question}  
  Show that the set of languages decidable in polynomial time is stable by intersection,
  union, complementation and star (i.e. the language $L^*$).
\end{question}

\section{One-way functions}

Let us suppose that :
\begin{itemize}

\item we have $f$ a one-to-one function over integers with $n$ bits
  towards integers with $n$ bits for all $n$ (i.e., given an input $x$
  with $n$ bits, $f(x)$ is an integer with $n$ bits such that
  $f(x)=f(y) \Rightarrow x=y$);

\item $f$ can be computed in polynomial time;

\item the inverse function of $f$ cannot be computed in polynomial
  time. (It is thus called a one-way function).
\end{itemize}

\begin{question}

  Show that, if such a function exists then $\DP\neq \NP$
  
  \hfill \emph{Suggestion~: Show that the language $L = \{(x,f(y)) : x
    < y \}$ belongs to $\NP\setminus\DP$.}
\end{question}

\begin{question}
  Such that, if such a function exists, then $\NP\cap \coNP\neq \DP$.
\end{question}

\section{Quines}

Given two TM $A$ et $B$ we note $A\cdot B$ a TM executing $B$ after
having executed $A$.

For each $w\in\Sigma^*$, let $P(w)$ be a TM over $\Sigma$ writing $w$ on the tape.

\begin{question}
  Justify with $q: \mathbb{N} \rightarrow \mathbb{N}$ is computable?

  $$ 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{question}
  Justify why $s_2(m,n) : \mathbb{N}^2 \rightarrow \mathbb{N}$ is computable
  $$ 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{question}
  Deduce from the previous questions that there exists a TM $M$ that
  halts by printing $\code{M}$ on the tape.
\end{question}


\end{document}

