\documentclass{article}
\usepackage{amsmath,amsthm}
\usepackage{amssymb,latexsym}
\usepackage{epsfig}
\usepackage{hyperref}
\usepackage{float}
\usepackage{fullpage}
\usepackage{enumerate}
\usepackage{paralist}
\usepackage{graphicx}


\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{assumption}[theorem]{Assumption}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{alg}[theorem]{Algorithm}
\newtheorem{protocol}[theorem]{Protocol}
\newtheorem{problem}[theorem]{Problem}

\newcommand{\ip}[2]{\left\langle #1 , #2\right\rangle}
\newcommand{\tr}{\trace}
\newcommand{\setft}[1]{\mathrm{#1}}
\newcommand{\lin}[1]{\setft{L}\left(#1\right)}
\newcommand{\density}[1]{\setft{D}\left(#1\right)}
\newcommand{\unitary}[1]{\setft{U}\left(#1\right)}
%\newcommand{\trans}[1]{\setft{T}\left(#1\right)}
\newcommand{\herm}[1]{\setft{Herm}\left(#1\right)}
\newcommand{\pos}[1]{\setft{Pos}\left(#1\right)}
\newcommand{\sep}[1]{\setft{Sep}\left(#1\right)}
\newcommand{\rank}[1]{\operatorname{rank}(#1)}
\newcommand{\ex}{\paragraph{Exercise.}}


\def\I{I}
\def\({\left(}
\def\){\right)}
\def\X{\mathcal{X}}
\def\Y{\mathcal{Y}}
\def\Z{\mathcal{Z}}
\def\W{\mathcal{W}}
\def\yes{\text{yes}}
\def\no{\text{no}}
\def\blog{\textup{log}}
\newcommand{\A}{\spa{A}}
\newcommand{\B}{\spa{B}}
\newcommand{\UA}{U_A}


\newcommand{\myparagraph}[1]{\paragraph{#1.}}

\newcommand{\eps}{\varepsilon}
\newcommand{\epssdp}{\varepsilon_{\rm sdp}}
\newcommand{\bra}[1]{\langle #1|}
\newcommand{\ket}[1]{|#1\rangle}
\newcommand{\braket}[2]{\langle #1|#2\rangle}
\newcommand{\ketbra}[2]{\ket{#1}{\bra{#2}}}
\newcommand{\lmin}[1] {\lambda_{\operatorname{min}}(#1)}
\newcommand{\lmax}[1] {\lambda_{\operatorname{max}}(#1)}
\newcommand{\lhyes} {\operatorname{LH_{yes}}}
\newcommand{\lhno} {\operatorname{LH_{no}}}
\newcommand{\CQ}{\mathcal{CQ}}
\newcommand{\lh}{\operatorname{LH}}
\newcommand{\flh}{\operatorname{5-LH}}
\newcommand{\klhh}{\operatorname{k-LH}}
\newcommand{\qma}{\operatorname{QMA}}
\newcommand{\enc}[1]{\left<#1\right>}

\newcommand{\C}{C}
\newcommand{\Id}{Id} %CHECK
\newcommand{\Exs}[2]{E_{#1}[#2]} %CHECK

\newcommand{\beq}{\begin{equation}}
\newcommand{\eeq}{\end{equation}}

\newcommand{\trace}{{\rm Tr}}

\newcommand{\norm}[1]{\left\|\,#1\,\right\|}       % norm
\newcommand{\pnorm}[1]{\left\|\,#1\,\right\|_p}       % norm
\newcommand{\onorm}[1]{\norm{#1}_{\mathrm{1}}}      % Euclidean norm for vectors
\newcommand{\enorm}[1]{\norm{#1}_{\mathrm{2}}}      % Euclidean norm for vectors
\newcommand{\trnorm}[1]{\norm{#1}_{\mathrm {tr}}}  % trace norm
\newcommand{\fnorm}[1]{\norm{#1}_{\mathrm {F}}}    % frobenius norm
\newcommand{\snorm}[1]{\norm{#1}_{\mathrm {\infty}}}    % spectral norm

\newcommand{\set}[1]{{\left\{#1\right\}}}    % braces for set notation
\newcommand{\ve}[1]{\mathbf{#1}}
\newcommand{\abs}[1]{\left\lvert #1 \right\rvert}
\newcommand{\optprod}{\OPT_P}
\newcommand{\opt}{\operatorname{OPT_1}}
\newcommand{\optt}{\operatorname{OPT_2}}
\newcommand{\newopt}{\operatorname{NEW-OPT}}
\newcommand{\swap}{\operatorname{SWAP}}
\newcommand{\poly}{\operatorname{poly}}
\newcommand{\cc}{d^{\frac{k}{2}}}
\newcommand{\OPT}{{\rm OPT}}
\newcommand{\QMA}{{\rm QMA}}
\newcommand{\MQA}{{\rm MQA}}
\newcommand{\NP}{{\rm NP}}
\newcommand{\PP}{{\rm P}}
\newcommand{\PH}{{\rm PH}}
\newcommand{\BPP}{{\rm BPP}}
\newcommand{\BQP}{{\rm BQP}}

\newcommand{\complex}{{\mathbb C}}
\newcommand{\reals}{{\mathbb R}}
\newcommand{\ints}{{\mathbb Z}}
\newcommand{\nats}{{\mathbb N}}

\newcommand{\spa}[1]{\mathcal{#1}}
\newcommand{\dens}{\mathcal{D}(\spa{A}\otimes\spa{B})}

\newcommand{\LL}{\mathcal{L}}
\newcommand{\DD}{\mathcal{D}}
\newcommand{\HH}{\mathcal{H}}
\newcommand{\UU}{\mathcal{U}}

\newcommand{\klh}{MAX-$k$-local Hamiltonian}

\mathchardef\mhyphen="2D

\newcommand{\ayes}{A_{\rm yes}} %CHECK
\newcommand{\ano}{A_{\rm no}} %CHECK
\newcommand{\nl} {\mathcal{L}_1}


\bibliographystyle{alpha}

\begin{document}

\title{\vspace{-10mm}Quantum Complexity Theory, UPB\\Summer 2020, Assignment 1\\{\large To be completed by: Tuesday, November 10, start of tutorial}}
\date{}
\maketitle

\section{Exercises}

\begin{enumerate}
    \item \textbf{Turing Machines (TMs).} One of the reasons the TM model is highly revered is due to its \emph{robustness}, i.e. the fact that its computational power does not change much under small changes to the model.
            \begin{enumerate}
                \item In class, we defined a TM as moving its head either one cell to the left (L) or one cell to the right (R) in one computation step. Prove that adding a third option, that the head can stay (S) put in a computation step, does not increase the power of the model. In other words, show how our ``standard'' TM model from class can simulate the option of keeping the head stationary.
                \item Our standard TM model assumes access to a single work tape. Another option is to allow \emph{two} work tapes, each with its own independent head. Show that our standard TM model can simulate a $2$-tape TM.
            \end{enumerate}
    \item \textbf{Languages and decision problems.} In class, we associated each language $L\subseteq\set{0,1}^*$ with a decision problem $\Pi_L$ of the form: Given $x\in\set{0,1}^*$, is $x\in L$? Let us flesh out how this framework can be used to encode real-life decision problems that \emph{a priori} have nothing to do with languages.

            We begin with an example. Recall the Halting Problem asks: Given as input a description of a TM $M$ and input $x\in\set{0,1}^*$, does $M$ halt on input $x$? The corresponding language for this is
            \[
                \operatorname{HALT} = \set{\langle M,x\rangle \mid M\text{ is a TM},~x\in\set{0,1}^*,\text{ and $M$ halts on input $x$}}.
            \]
            The angle brackets $\langle\cdot\rangle$ mean we are implicitly applying a fixed encoding scheme mapping (say) the input Turing machine $M$ to a binary string.
            \begin{enumerate}
                \item Convince yourself that deciding membership in HALT is equivalent to solving the Halting Problem.
                \item Write down the language $L$ corresponding to the problem FACTOR from lecture.
            \end{enumerate}
    \item \textbf{P and NP.}
    \begin{enumerate}
        \item Prove that $\PP\subseteq \NP$.
        \item Prove that $\PP$ is closed under complement. In other words, prove that a language $L\subseteq\set{0,1}^*$ is in $\PP$ if and only if $\overline{L}:=\set{0,1}^*\setminus L$ is in $\PP$.
        \item Is NP closed under complement? Why or potentially why not?
        \item Suppose we change the definition of NP so that the proof $y$ has length only \emph{logarithmic} in the input size, $n$, instead of polynomial in $n$. (Everything else about the definition of NP does not change.) Call this class ShortNP. What can you say about ShortNP versus P?
        \item Suppose we change the definition of NP so that the proof $y$ has length  \emph{exponentially long} in the input size, $n$, instead of polynomial in $n$. (Everything else about the definition of NP does not change.) Call this class LongNP. What can you say about LongNP versus NP?
    \end{enumerate}

    \item \textbf{Reductions and NP-completeness.} The language INDEPENDENT-SET is defined as follows:
    \[
        IS=\set{\enc{G,k}\mid G=(V,E)\text{ has an independent set $S$ of size at least }k}.
    \]
    Here, $S\subset V$ is an \emph{independent set} if for any $v,w\in S$, $v$ and $w$ are not connected by an edge (i.e. $(v,w)\not\in E$).
    \begin{enumerate}
        \item Show that $IS\in\NP$ by demonstrating the existence of an efficiently checkable proof for YES-instances of the problem.
        \item Below, we sketch a reduction from 3-SAT to IS. Given a 3-CNF formula $\phi$ consisting of $k$ clauses, we construct a graph $G$ as follows:
            \begin{itemize}
                \item For each clause $\phi_i$, we add a triangle gadget $\Delta_i$ to $G$, whose vertices correspond to the literals of $\phi_i$.
                \item We connect vertices corresponding to conflicting literals with an edge.
            \end{itemize}
            For example, suppose
            \[\phi=(x_1\vee x_2 \vee x_3)\wedge(\overline{x_5}\vee \overline{x_3}\vee x_4)\wedge(x_5\vee\overline{x_2}\vee x_6).\] Then, $G$ is given by:
            \begin{center}
            \includegraphics[height=40mm]{reduction2.pdf}
            \end{center}

            \vspace{2mm}
            \begin{enumerate}
                \item Prove that if $\phi$ is satisfiable, then $G$ has an independent set $S$ of size $k$.
                \item Prove that if $G$ has an independent set $S$ of size $k$, then $\phi$ is satisfiable.
            \end{enumerate}
    \end{enumerate}
\end{enumerate}
\end{document}
