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

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

\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 $\P = \NP$ then the problem of determining
  whether or not a given integer is prime is solvable in polynomial
  time.  Explain briefly.

\vspace{1.2in}

\item True or false: If $L$ is polytime reducible to a finite
  language, then $L$ is in $P$.  Explain briefly.

\vspace{1.2in}

\item True or false: There is no language in $\NP$ that is
  recognizable in less than linear time.  (That is, requiring less
  than $n$ steps for inputs of length $n$.)  Explain briefly.

\vspace{1.2in}

\item If the complement of the reverse of a language $L$ is
  recognizable in polynomial time, and if $L$ is in $\NP$, then the
  set of palindromes in $L$ is recognizable in polynomial time.  (A
  palindrome is equal to its reversal.) Explain briefly.

\vspace{1.2in}

\item It is $\NP$-complete to determine if a given input formula has
  two or more satisfying assignments. Explain briefly.

\end{enumerate}
\end{problem}


\newpage

\begin{problem} \textbf{(15 points)}
Show the following language to be $\NP$-complete:
$$\mathit{SETPACK} = \cset{\rep{S,C,k}}{\parbox{3in}{$S$ is a finite
    set, $C$ is a collections of subset of $S$, and $k$ is an integer
    such that $C$ contains $k$ mutually disjoint sets}}$$
Hint: Consider $\mathit{X3C}$.
\end{problem}


\newpage


\begin{problem} \textbf{(15 points)}
  The $\mathit{SQUARESUM}$ problem is as follows: you have before you
  a set of integers $a_1$, $a_2$, \ldots $a_n$, an integer $K$ and an
  integer $J$. You must determine if you can put the integers $a_1$
  through $a_n$ into disjoint sets $A_1$ through $A_K$ so that
  $$ \sum_{i=1}^K \left( \sum_{a \in A_i} a\right)^2 \leq J$$
  Show that $\mathit{SQUARESUM}$ is $\NP$-complete. (Hint: consider
  the case where $K=2$.)
\end{problem}

\newpage


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



\newpage


\begin{problem} \textbf{(15 points)}
We say that two languages, $L_1$ and $L_2$ are \emph{polynomial time 
  isomorphic} if there exists a mapping $f: \Sigma^* \rightarrow
\Sigma^*$ such that:
\begin{enumerate}
\item $f$ is a bijection,
\item $f$ is a poly-time mapping from $L_1$ to $L_2$, and
\item $f^{-1}$ is a poly-time mapping from $L_2$ to $L_1$.
\end{enumerate}
It is conjectured that every $\NP$-complete language is polynomial
time isomorphic to every other $\NP$-complete language. Prove that if
this were the case, then $\P \not = \NP$.
\end{problem}

\end{document}




