\documentclass{article}
\input{6045preamble}
\usepackage{fancyheadings}

\begin{document}
\handout{15}{Prof. Ron Rivest}{}{}{Handout 15: Quiz 3}

\Large
Write your full name on each page.
\normalsize

\newpage
\pagestyle{fancy}
\lhead[Name:\hspace{2in}]{Name:\hspace{2in}}
\cfoot[]{}
\begin{problem}
\textbf{Trick Questions: (3 points each)}
\begin{enumerate}


\item True or false: If all the functions $f_1, f_2, f_3 \cdots$ are
  all polynomial time computable, then the function $g(x) \eqdef
  f_1(f_2(\cdots f_{|x|}(x) \cdots))$ (i.e., on input of length $n$ we
  apply the first $n$ functions) is also polynomial time
  computable. Briefly explain your answer.
\vspace{1.2in}
  

\item Give a language $L \in \NP$ such that $L \pred \overline{L}$.
\vspace{1.2in}

\item True or false: If $A \pred B$, $B \pred C$ and both $A$ and $C$
  are $\NP$-complete, than $B$ is $\NP$-complete. Briefly explain your
  answer.


\vspace{1.2in}

\item True or false: The problem of determining if a graph $G$ has a
  7-clique is $\NP$-complete. Briefly explain your answer.

\vspace{1.2in}

\item True or false: Given a set $S$ of integers, the problem of
  deciding if it can be partitioned into 3 disjoint subsets that share
  the same sum is $\NP$-complete. Briefly explain your answer.

\end{enumerate}
\end{problem}


\newpage

\begin{problem} \textbf{(15 points)}
Show the following language to be $\NP$-complete:
$$\mathit{GRAPH-EMBED} = \cset{\rep{G_1, G_2}}{\parbox{3in}{$G_1$ and
    $G_2$ are undirected graphs and $G_2$ can be embedded in $G_1$}}$$
(A graph $B$ can be embedded in a graph $A$ iff $B$ can be made into a
sub-graph of $A$ simply by relabeling the nodes.  That is, $B$ can be
embedded in $A$ iff there exists a function $f$ from nodes in $B$ to
nodes in $A$ such that there is an edge between nodes $n_1$ and $n_2$
in $B$ iff there exists an edge between $f(n_1)$ and $f(n_2)$ in $A$.)
Hint: Consider $\mathit{CLIQUE}$.
\end{problem}


\newpage


\begin{problem} \textbf{(15 points)}
  The $\mathit{SHOPLIFTER}$ problem is as follows: you have before you a
  set of objects $n_1$, $n_2$, \ldots $n_k$. Each object has a
  \emph{size} $s_1$, $s_2$, \ldots $s_k$ and a \emph{value} $v_1$,
  $v_2$, \ldots $v_k$. You have a backpack that has a size limit $B$
  and a value goal $V$. Find a set of objects $S$ that fit into your
  backpack
  $$\sum_{n_i \in S} s_i \leq B$$
  whose collective value is above the value goal:
  $$\sum_{n_i \in S} v_i \geq V$$
  Show that $\mathit{SHOPLIFTER}$ is $\NP$-complete. (Hint: consider
  the case where $s_i = v_i$ for all $i$.)
\end{problem}

\newpage


\begin{problem} \textbf{(15 points)}
Show that if $\P = \NP$, there exists a polynomial time algorithm
that takes in an undirected graph $G$ and returns either
\begin{itemize}
\item A Hamiltonian cycle in $G$, if one exists, or
\item A special output $\perp$ if one does not.
\end{itemize}
Note that your algorithm must return the cycle itself!
\end{problem}



\newpage


\begin{problem} \textbf{(15 points)}
Recall the class of languages $\coNP$:
$$L \in \NP \iff \overline{L} \in \coNP$$
A language $L$ is
$\coNP$-complete iff
\begin{enumerate}
\item $L \in \coNP$, and
\item $\forall A \in \coNP$, $A \pred L$.
\end{enumerate}
Consider the language
$$\mathit{TAUT} = \cset{\phi}{\phi \mbox{ is a boolean formula and
    $\phi$ is true under every assignment}}$$
Show that $\mathit{TAUT}$ is $\coNP$ complete. (You can assume the
language $$\mathit{BOOL} = \cset{w}{w \mbox{ is a boolean formula }}$$
is in $\P$.)

\end{problem}

\end{document}




