\documentclass{scrartcl}
\usepackage[margin=1in, left=0.5in, right=0.5in]{geometry}
\usepackage[utf8]{inputenc}
\usepackage[english]{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]{December the 14th, 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{Reducing from CNF-SAT to HAMPATH}

A path from $s$ to $t$ in a graph $G$ is hamiltonian when the path
goes through all nodes exactly once. The $HAMPATH$ problem is defined
as:
$$HAMPATH = \{ (G,s,t) \mid \mbox{ there exists an hamiltonian path in the oriented
  graph } G \mbox{ from } s \mbox{ to } t\}$$

\begin{question}
  Show that $HAMPATH$ is $\NP$-complete.
\end{question}

\emph{Suggestion: start from a CNF-SAT formula with $k$ clauses and
  $l$ variables. Build a graph with (for $i$ a variable and $j$ a
  clause): 3 nodes $x_i^j$, $\bar{x}_i^j$ et $n^i_j$; 2 nœuds $s_i$
  and $n^0_i$; 1 node $C_j$ plus one node $s_{l+1}$ using the
  following gadgets:}
\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{Variable gadget}
\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 for $x_i$ used in $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 for $\bar{x}_i$ used in $C_j$ }
\label{fig:color}
\end{center}
\end{subfigure}
\end{subfigure}
\end{figure}

\begin{question}
  Show that the $HAMPATH$ problem stays $\NP$-complete if we remove the
  orientedness of the graphs considered.
\end{question}

\section{Time hierarchy theorem}

In this section, we will consider 2-tape deterministic Turing
machines. We select a coding $\code{M}$ for the Turing machine
$M$. For instance, $\code{M}$ codes the states with words of
$\{0,1\}^*$, the tape alphabet with words of $\{\alpha,\beta\}^*$,
heads direction with $\{<,>,\_\}^2$. A TM is then represented with a
sequence of transitions for each state. For the state $e$, we
represent it as $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|$ where the $e, (e_i)_i$ are the states, the
$(a_i)_i,(b_i)_i,(c_i)_i,(d_i)_i$ are all words in both tape and the
$(f_i)_i$ are the directions. $a$ (resp. $b$) is the letter read on
the first tape (resp. second tape) during the transition and $c$
(resp. $d$) is the letter written on the first tape (resp. second tape).

\begin{defi}
  The set $TIME(f(n))$ corresponds to the set of problems for which
  there exists a Turing machine deciding them in less than $f(n)$
  computing steps over inputs of size $n$.
\end{defi}

In the same manner that we say that sorting can be done in $O(n\times
  ln(n))$ (and thus omitting to say ``when the input has size $n$'',
  we always write $TIME(f(n))$ but this should be read as
  $TIME(n\rightarrow f(n))$ because the $n$ represents the size of the
  input.

In the remaining part of the TD, when needed, you can use the linear
speedup theorem stating that for all $g$ and all $\epsilon > 0$
\textbf{fixed}, we have $TIME(g(n))\subseteq TIME(n+2+\epsilon g(n))$.

\begin{defi}
  A function $f$ is \emph{time constructible} when there exists a
  machine $M$ taking $1^n$ as input and producing $f(n)$ in time
  $f(n)$.
\end{defi}

The time hierarchy theorem states that when $f$ is a time
constructible function then: $$TIME\left(o\left(\dfrac{f(n)}{log
  f(n)}\right)\right)\subsetneq TIME(f(n))$$

\emph{We will demonstrate here a lighter version of the theorem:
  $TIME(f(n))\subsetneq TIME(f(2n+1)^3)$ with $n^3\leq f(n)$.}

For $f$ time constructible, we define $Halt_f = \{ \code{M}\#x \mid M
\mbox{ accepts } x \mbox{ in } f(|x|) \mbox{ steps}\}$.


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

Let us suppose that $Halt_f\in TIME\left(\dfrac{f(\lfloor n/2
  \rfloor)}{2}\right)$. Let $K$ be a TM deciding $Halt_f$ in time
$f(\lfloor n/2 \rfloor)/2$, we can build $D_K$ taking $\code{M}$ as
input and running $K$ on $\code{M}\#\code{M}$. $D_K$ accepts when $K$
refuses and refuses when $K$ accepts.

\begin{question}
Justify that $D_K$ can be built such that $D_K \in TIME(f(n))$.
\end{question}

\begin{question}
Justify that $D_K$ can not exists using a diagonalization argument.
\end{question}

\begin{question}
Conclude that $TIME(f(\lfloor n/2 \rfloor)/2)\subsetneq TIME(f(n)^3)$.
\end{question}

\begin{question}
  Show that $P\subsetneq EXPTIME \subsetneq 2-EXPTIME$.

  \emph{We recall: $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}


\section{An $EXPTIME$-complete problem}

\begin{question}
Justify that $f(x)=2^x$ is time constructible and show that $Halt_f\in EXPTIME$. 
\end{question}

\begin{question}
  Let $L\in EXPTIME$, show that $L$ is polynomial time reductible to
  $Halt_f$ and thus prove that $Halt_f$ is $EXPTIME$-complete.
\end{question}

\section{A $PSPACE$-complete problem}

The set of Quantified Boolean Formulæ (QBF) is defined by induction as:
\begin{itemize}
  
\item all propositional variables are QBF;
  
\item if $\phi$ is QBF then $\lnot \phi$ also is QBF;
  
\item if $\phi$ and $\psi$ are QBF then $\phi \land \psi$ is QBF
  
\item if $\phi$ is QBF and $p$ is a propositional variable then
  $\forall p\phi$ and $\exists p\phi$ are QBF
\end{itemize}

QBF are equipped with their usual Boolean valuation. The language of
$TQBF$ is the language of QBF evaluating to true.

\begin{question}
  Show that $TBQF$ is $PSPACE$-complete.
\end{question}

Suggestion for $PSPACE$ hardness: start from $L\in PSPACE$. Show that
$L$ is decided by $K$ for which it exists $P\in \mathbb{N}[X]$ such
that on an input of size $n$, $K$ decides in time $2^{P(n)}$ and space
$P(n)$. Reduce $L$ to $TQBF$. Encode the state of $K$ and its memory
with a $P(n)$ uplet of $\{0,1\}$ and build a formula $\Phi(c_1,c_2,
t)$ describing whether $K$ can move from the state $c_1$ to $c_2$ in
time $2^t$ (use a fast exponentiation).

\end{document}

