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

\newcommand{\ZETTELNUMMER}{4}
\newcommand{\ABGABEDATUM}{on 24. 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 {NP and coNP} {10 points}

\begin{enumerate}
\item Show that the following language is NP-complete:
\[
  \{(\langle M \rangle, w, 1^m) \mid \text{$M$ is a nondeterministic 
  TM accepting $w$ in $\leq m$ steps}\}.
\]
 
\item Recall that $\text{coNP} := \{\{0,1\}^* \setminus L \mid L \in \text{NP}\}$.

What is the difference between coNP and $2^{\{0,1\}^*} \setminus \text{NP}$?

Prove the alternative characterization of \text{coNP}:
a language $L \subseteq \{0,1\}^*$ is in coNP if and only if there
exists a deterministic polynomial time 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 \forall y \in \{0,1\}^*, |y| \leq |w|^c:
\, V(w,y) \text{ accepts.}
\]

\end{enumerate}

\AUFGABE{Unary Languages I}{10 points}

A language $L \subseteq \{0\}^*$ is called \emph{unary}.
We would like to show that unary NP-complete problems are unlikely to exist.
\begin{enumerate}
\item  Suppose we have a polynomial time algorithm to decide 3SAT. Show that
  there also exists a polynomial time algorithm to compute a satisfying
  assignment for any satisfiable 3SAT formula.
\item Suppose that $L \subseteq \{0\}^*$ is NP-complete. This means 
  that $\text{3SAT} \leq_p L$,
  so there exists a function $f : \{0,1\}^* \rightarrow \{0\}^*$ such that
  (i) $f$ is computable in polynomial time, and (ii) 
  $\psi \in \text{3SAT} \Leftrightarrow f(\psi) \in L$ for every Boolean formula $\psi$.
  Use $f$ to design a polynomial time algorithm for 3SAT.

  \emph{Hint}: Let $X := \{0,1\}^{\leq n}$. How large can $f(X)$ be?
    Let $\psi$ be a Boolean formula. To decide whether $\psi$ is satisfiable, try an 
    approach similar to (a). Use $f$ and a dynamic-programming-type approach 
    to reduce the size of the search tree.
\item Conclude that if there exists an NP-complete unary language, then 
  $\text{P} = \text{NP}$.
\end{enumerate}

\AUFGABE{Unary Languages II}{10 points}

Show that if $\text{NP} \cap 2^{\{0\}^*} \subseteq \text{P}$, 
then $\text{EXP} = \text{NEXP}$.
Interpret the result.
\end{description}

\end{document}
