\documentclass[a4paper,twoside,12pt]{article}
%\usepackage [reqno] {amsmath}
\usepackage{amsfonts,amstext,amssymb}
\usepackage{amsmath}
\usepackage{german}
\usepackage{graphicx}
\usepackage{fullpage}

\newcommand{\ZETTELNUMMER}{3}
\newcommand{\ABGABEDATUM}{on 17. May 2016 in the tutorial session}

\newcounter{AUFGNR}
\setcounter{AUFGNR}{1}
\newcommand{\AUFGABE}[2]{\vspace{0.3cm}\item[Problem~\arabic{AUFGNR}]\stepcounter{AUFGNR} #1\hfill\emph{#2}}


\newcommand{\floor}[1]{\left\lfloor{#1}\right\rfloor}
\newcommand{\ceil}[1]{\left\lceil{#1}\right\rceil}
\newcommand{\half}[1]{\frac{#1}{2}}
\newcommand{\eps}{\varepsilon}
\newcommand{\N}{\mathbb{N}}



\renewcommand{\labelenumi}{(\alph{enumi})}
\renewcommand{\labelenumii}{(\roman{enumii})}


\begin{document}
\pagestyle{empty}
\hrule\medskip
\rule{0ex}{0ex}\\[-1ex]
\ZETTELNUMMER. Assignment on 

\smallskip
\noindent
\large
\textbf{Computational Complexity Theory}\hfill SoSe 2016 \\[0.5ex]
\normalsize
Wolfgang Mulzer, Claudia Dieckmann

\medskip\hrule

\smallskip
\noindent
\textbf{Due} \ABGABEDATUM

\vskip 0.5cm


\begin{description}
\AUFGABE {Relationships Between Complexity Classes} {10 points}

\begin{enumerate}
\item Show that $\text{NP} \neq \text{DSPACE}(n)$.
 

\noindent\emph{Hint}: We know that NP is closed 
under polynomial-time reductions.  What about 
$\text{DSPACE}(n)$?

\item Show that $\text{EXP} \neq \text{NEXP} \Rightarrow 
\text{P} \neq \text{NP}$.

\noindent\emph{Hint}: Use padding to prove the 
contrapositive $\text{P} = \text{NP} \Rightarrow 
\text{EXP} = \text{NEXP}$.
\end{enumerate}

\AUFGABE{Single-tape Turing Machines I}{10 points}

Let $T : \N \rightarrow \N$ be time-constructible, 
and let $\text{NTIME}_1(T)$  be the set of languages 
that can be decided in $O(T(n))$ time by a non-deterministic 
Turing machine \emph{with only one (read-write) tape.}
$\text{DTIME}_1(T)$  is defined similarly.

Let $L := \{x0^{n}y \mid n \in \N,\quad x,y \in \{0,1\}^n, \quad x \neq y\}$. 
Show that $L$ is contained in $\text{NTIME}_1(n \log n)$.

\noindent\emph{Hint}: First, show that $L$  can be 
decided in $O(n)$ time by a non-deterministic 
Turing machine with two tapes, where the second 
tape contains only $O(\log n)$ cells. Then show 
how to simulate this machine by a single-tape 
non-deterministic Turing machine in $O(n \log n)$ time.


\AUFGABE{Single-tape Turing Machines II}{10 points}

Let $L$ be defined as in the second problem. We will 
now show that any deterministic Turing machine with 
a single work tape requires $\Omega(n^2)$ time to
decide $L$. 

\begin{enumerate}
\item
Let $L' := \{x0^{n}x \mid n \in \N,\quad x \in \{0,1\}^n\}$. 
Show that if there exists a deterministic single-tape 
Turing machine that decides $L$ in time $T(n)$, then 
there is a deterministic single-tape Turing machine that decides
$L'$ in time $T(n) + O(n \log n)$.

\item 
Let $M'$ be a Turing machine that decides $L'$ in 
time $T'(n)$. Let $i \in \N$ and $x \in \{0,1\}^n$.  
We define the $i$\textsuperscript{th} \emph{crossing 
sequence} for $M'$ on $x$: let $t_1$ be the first 
time that $M'$ on input $x0^nx$ goes from cell $i$ to 
cell $i+1$; let $t_2$ be the first time that $M'$ goes 
from cell $i+1$ to $i$; let $t_3$ be the second time that $M'$ 
goes from $i$ to $i+1$; let $t_4$ be the second time that $M'$ 
goes from $i+1$ to $i$; etc. Let $t_m$ be the last 
time that $M'$ crosses from cell $i$ to $i+1$ or back. 
Clearly, we have $t_1 < t_2 < t_3 < \dots < t_m$.

The $i$\textsuperscript{th} crossing sequence is 
the sequence $( q_1, q_2, \dots, q_m)$,
where $q_j$ is the state of $M'$ at time $t_j$. 
We call $m$ the \emph{length} of the crossing sequence.

Argue that for any input $x0^nx$, there has to 
be an $i \in \{n, \dots, 2n-1\}$ such that the 
$i$\textsuperscript{th} crossing sequence on $x$ 
has length at most $T'(n)/n$.

\item Let $x \neq y \in \{0,1\}^n$. Show that for every  
$i \in \{n, \dots, 2n-1\}$ the $i$\textsuperscript{th} 
crossing sequence for $M'$ on $x$ must be different 
from the $i$\textsuperscript{th} crossing sequence for 
$M'$ on $y$. Conclude that for every $x \in \{0,1\}^n$ 
and for every $i \in \{n, \dots, 2n-1\}$, the length 
of the $i$\textsuperscript{th} crossing sequence on 
$x$ must be $\Omega(n)$.

\item Conclude that $T'(n) = \Omega(n^2)$, so $\text{DTIME}_1(n \log n) 
\subsetneq \text{NTIME}_1(n \log n)$.
\end{enumerate}

\emph{Remark}: For multi-tape Turing machines,
Paul, Pippenger, Szemeredi, and Trotter showed that 
$\text{DTIME}(n) \subsetneqq \text{NTIME}(n)$, but 
the proof is much harder, and the
gap is minuscule (about $\log^* n$).

\end{description}
\end{document}
