\documentclass{article}
\input{6045preamble}


\begin{document}
\handout{16}{Prof. Ron Rivest}{25 April 2002}{Jonathan
  Herzog}{Handout 16: Recitation Problems}

\begin{enumerate}
\item Show that $4-\mathit{SAT}$ is $\NP$-complete.
\item An \emph{independent set} in a graph $G$ is a set $S$ of nodes such
  that no two nodes in $S$ have an edge connecting them. Let
  $$\mathit{INDSET} = \cset{\rep{G, k}}{G \mbox{ is a graph with an
      independent set of size } k}$$
  Show that $\mathit{INDSET}$ is $\NP$-complete.
\item Recall $\mathit{MAXCLIQUE}$ from the homework:
  $$\mathit{MAXCLIQUE} = \cset{\rep{G,k}}{\mbox{the largest clique of
      $G$ has $k$ nodes}}$$
  Show that if $\P = \NP$, then one can find the largest clique of a
  graph $G$ in polynomial time.
\item One form of \emph{traveling salesman problem} is the decision
  form: 
  \begin{quotation}
    Given a fully connected graph $G$ with (integer) weighted edges,
    and an integer $k$, does there exist a Hamiltonian cycle of total
    weight $k$?
  \end{quotation}
  This problem is $\NP$-complete. Show that if $\P = \NP$, then one
  can find the length of the ``shortest'' Hamiltonian of a graph $G$
  in polynomial time.

\end{enumerate}
\end{document}
%%% Local Variables: 
%%% mode: latex
%%% TeX-master: t
%%% End: 
