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

\newcommand{\ZETTELNUMMER}{5}
\newcommand{\ABGABEDATUM}{on 31. 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 {NL} {10 points}

\begin{enumerate}
\item 
Analyze the running time of Savitch's algorithm for the
$st$-path problem.
 
\item 
Show the following properties of LOGSPACE-reductions.
Let $L_1, L_2, L_3 \subseteq \{0,1\}^*$. 
\begin{enumerate}
  \item 
If $L_1 \leq_L L_2$ and $L_2 \leq_L L_3$, then 
$L_1 \leq_L L_3$.
\item
  If $L_2 \in \text{LOGSPACE}$ and $L_1 \leq_L L_2$, then
  $L_1 \in \text{LOGSPACE}$
\end{enumerate}

\end{enumerate}

\AUFGABE{2SAT}{10 points}

In 2SAT, we are given a Boolean formula in CNF such that each
clause contains at most 2 literals.
Let $\Psi$ be a 2SAT-formula, and let $(l_1 \vee l_2)$
be a clause in $\Psi$, where $l_1$ and $l_2$ are (not necessarily distinct!) literals. 
The clause $(l_1 \vee l_2)$ can also be interpreted as the
\emph{implications} $\neg l_1 \rightarrow l_2$ resp.\
$\neg l_2 \rightarrow l_1$. 

This observation inspires the following definition.
The \emph{implication graph} $G_\Psi$ for $\Psi$ is a directed graph.
For each variable $x$ in $\Psi$, 
there are two vertices, namely $x$ and $\neg x$.
For each 
clause $(l_1 \vee l_2)$ in $\Psi$ there are two edges, one from
$\neg l_1$ to $l_2$ and one from $\neg l_2$ to $l_1$ (where
we interpret $\neg\neg x$ as $x$). 

\begin{enumerate}
\item Show that $\Psi$ is unsatisfiable if and only if
  there exists a variable $x$ such that
  $G_\Psi$ has a directed cycle that contains both $x$ and $\neg x$.
\item Show that $\text{2SAT}$ is $\text{NL}$-complete.
\end{enumerate}

\AUFGABE{Sublogarithmic Space}{10 points}

Let $S: \N \rightarrow \N$ with $S(n) = o(\log\log n)$. Show
that $\text{DSPACE}(S) = \text{DSPACE}(1)$.

\emph{Hint}: Suppose that $L \in \text{DSPACE}(S)$, and let $M$ be
a  TM that decides $L$ with $\text{space}_M(n) \leq S(n)$.

Recall the definition of a \emph{crossing sequence} from Problem 3.3.
Give an appropriate definition for a crossing sequence of the
$i$th cell \emph{on the input tape} that also takes the state
of the work-tapes into account. Show  that the number of distinct crossing
sequences is at most $(2^{O(S(n))})^{2^{O(S(n))}} = o(n)$.

Now let $n_0$ be such that for $n \geq n_0$, we have 
$(2^{O(S(n))})^{2^{O(S(n))}} < n/3$, and for $n \leq n_0$, we have $S(n) < n_0$. 
Why does $n_0$ always exist?

If $\text{space}_M(n) < n_0$ for
all $n \in  \N$, we are done. Otherwise, let $w$ be a shortest word
for which $\text{space}_M(w) \geq n_0$. Note that $|w| \geq n_0$.  
Conclude that during the computation on $w$, there must be a crossing sequence that
occurs at least three times. Derive from this a contradiction to the choice
of $w$ as a shortest word with $\text{space}_M(w) \geq n_0$.


\end{description}
\end{document}
