\documentclass[12pt]{article}
\usepackage{fullpage}
\usepackage{epsfig}
\usepackage{latexsym}
\usepackage[all]{xy}
\begin{document}
\begin{center}
\bf
Algorithms\\
Computer Science 140 \& Mathematics 168\\
Instructor: B. Thom\\
Fall 2004\\
\rm
Homework 13a\\
Due on the day pigs fly.\\
\end{center}
\begin{enumerate}
\item {\bf [10 Points] Professor Lai and $NP$!}

\begin{enumerate}
\item 
Professor I. Lai claims that if $P_{1}$ and $P_{2}$ are any
two problems in $NP$ such that $P_{1} \leq_{p} P_{2}$, 
then $P_{2} \leq_{p} P_{1}$.  Prove that this would imply 
that $P = NP$.

		

\item 
Professor Lai is studying an interesting problem called
the Polygon Intersection Testing problem (PIT).  He claims
to have proved that PIT is NP-complete by showing that PIT
is in $NP$ and that $\mbox{PIT} \leq_{p} \mbox{VC}$ (VC is
the Vertex Cover problem).  Is this a valid approach for
proving that PIT is NP-complete?  Explain.



\end{enumerate}
\end{enumerate}
\end{document}
