\documentclass[12pt]{article}
\usepackage{fullpage}
\usepackage{epsfig}
\usepackage{latexsym}
\begin{document}
\begin{center}
\bf
Algorithms\\
Computer Science 140 \& Mathematics 168\\
Instructor: B. Thom\\
Fall 2003\\
\rm
Homework 12a\\
Due on 12/05/03 (2pm, my office)\\
\end{center}
\begin{enumerate}
\item {\bf [20 Points] HITTING SET!}
First, the gratuitous story:  The Computer Science Department at
The Western Institute of Technology (T.W.I.T.) has 5 faculty members,
Dr. I. ``Theo'' Rize, Dr. I. Dutu, Dr. Sam Heer, Dr. Mia Thue, and 
Dr. Juan More.  Each professor serves on a number of committees.
The Polynomial Time Algorithms Committee consists of Professors Rize, Dutu,
and More.  The NP-Completeness Committee consists of Professors
Dutu, Heer, and Thue.  Finally, the Other Stuff Committee consists
of Professors Thue and More.  The Dean would like to convene a meeting
in which the number of computer scientists invited is minimized
(she can't stand their bad CS jokes!)
but each committee is represented by at least one of its members.
For example, inviting Professors Thue and More would be a solution in
this case.

The Dean has formulated this problem as the following general problem (known
to computer scientists as the HITTING SET Problem):
We are given a set $S$ (the set of professors) and a collection, $C$, of
subsets of $S$ (the set of committees).
A hitting set for $C$ is a subset $S'\subseteq S$ such that $S'$ contains at least one element from each
subset in $C$.  The HITTING SET optimization problem is to find the
smallest hitting set.  


\begin{enumerate}
\item Formulate the HITTING SET decision problem
corresponding to the optimization problem described above.



\item In this part of the problem, you will prove 
that the HITTING SET decision problem
is NP-complete.  

\begin{enumerate}
\item The first part of proving NP-completeness
is to show that HITTING SET is in the class NP.
Briefly explain why this is true.
		


\item Next, we need to give a reduction
from some known NP-complete problem to 
the HITTING SET problem.  Describe a 
reduction from the Vertex Cover Problem.
			


\item Next, explain why this reduction
can be performed in polynomial time.
			

			
\item Finally, prove that your reduction is 
correct.  That is, you need to show that
the answer to an instance of VERTEX COVER is
true if and only if (that requires two
separate proofs!) the answer to the constructed
HITTING SET problem is true.  
			




\end{enumerate}
\end{enumerate}
\item {\bf [15 Points ] To be or not to be NPC!}
In class we introduced and explored the complexity classes NP, P, and NPC.
The million dollar yet unanswered question was also discussed: 
``Does (or does not) P equal NP?''. 
Below you're going to explore questions that may or may not relate to this issue.

\begin{enumerate}
\item If you were to discover some problem $x$ such that $x \in P$ and $x \in NPC$,
would it answer the million dollar question?
Explain your answer carefully.



\item Would it be worthwhile to discover some problem $x$ such that
$x \in P$ and $x \in NP$? Explain your answer carefully.



\item If you were able to prove that $NP = NPC$ would it answer the million dollar question?
Explain your answer carefully.



\item If you were able to prove that $NP \neq NPC$, would this answer the
million dollar question? Explain your answer carefully.



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