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

\newcommand{\ZETTELNUMMER}{6}
\newcommand{\ABGABEDATUM}{on 7. June 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{PSPACE and PH}{10 points}

\begin{enumerate}
  \item Complete our proof that TQBF is PSPACE-complete by showing that
    we can convert the resulting formula to prenex form in polynomial time.
  \item Show that if PH has complete problems, then the polynomial 
    hierarchy collapses. What does this say about the conjecture 
    $\text{PSPACE} = \text{PH}$? 
\end{enumerate}

\AUFGABE{Certificate Definition of NL}{10 points}

Consider the following attempt to define NL using
certificates:

A language $L \subseteq \{0,1\}^*$ is in bogusNL if and only if there
exists a deterministic \emph{logspace} Turing machine $V$ and a constant
$c \geq 1$, such that for every $w \in \{0,1\}^*$, we have
\[
w \in L \quad \Leftrightarrow \quad \exists y \in \{0,1\}^*, |y| 
\leq |w|^c:
\, V(w,y) \text{ accepts.}
\]

\begin{enumerate}
\item Show that $\text{SAT} \in \text{bogusNL}$.
  Is it likely that $\text{bogusNL} = \text{NL}$?
\item Explain what is wrong with the definition of bogusNL.
\item Give a better definition of NL in terms of
  certificates. Prove that your definition and 
  the definition you saw in class are equivalent.

\emph{Hint}: Use a special tape for the certificate.
\end{enumerate}
\AUFGABE{Alternation}{10 points}

An \emph{alternating} Turing machine (ATM) 
$M = (Q, \Gamma, \delta_0, \delta_1)$ is 
defined as follows: as usual, $M$ is a multitape 
Turing machine with input alphabet $\{0,1\}$ and 
tape alphabet $\Gamma$. Every state in $Q$ is 
either \emph{existential} or \emph{universal}.
There are three distinct special states 
$q_\text{start}, q_\text{yes}, q_\text{no} \in Q$.
In each step, $M$ can choose between $\delta_0$ 
or $\delta_1$ for the next transition. The ATM 
accepts a word $w$ if whenever $M$ is in an existential 
state, there \emph{exists} a choice of transition 
function that eventually leads to $q_\text{yes}$, and
if whenever $M$ is in a universal state \emph{both} 
choices of transition function 
eventually lead to $q_\text{yes}$.

\begin{enumerate}
  \item Interpret ATMs in terms of a binary tree that represents the 
    choices of transition function.
  \item The \emph{alternating time} $\text{atime}_M(w)$ 
  for an ATM $M$ on input $w$ is the \emph{maximum}
    number of steps over all transition function choices 
    until $M$ reaches a halting state $q_\text{yes}$ or 
    $q_\text{no}$. As usual, we define $\text{atime}_M(n)$ as
    the maximum of $\text{atime}_M(w)$ over all $w \in \{0,1\}^n$.

    Give easy interpretations of NP and coNP in terms of alternating TMs.

  \item
  We define AP as the class of all languages that can be decided 
  by an ATM in polynomial time.
  Show that $\text{AP} = \text{PSPACE}$. 

  \emph{Hint.} For $\text{AP} \subseteq \text{PSPACE}$, show 
  that every polynomial-time alternating Turing machine can be 
  simulated with polynomial space. For $\text{PSPACE} \subseteq \text{AP}$,
  begin by showing that there is an ATM that decides TQBF in 
  polynomial time. 
\end{enumerate}


\end{description}
\end{document}
