\documentclass[12pt]{article}
\usepackage{url}
\usepackage{graphicx}
\usepackage{fullpage}

\newcommand{\Bonus}[1]{\textbf{[#1 Points OPTIONAL Bonus Problem]}}
\newcommand{\Points}[1]{\textbf{[#1 Points]}}
\newcommand{\Name}[1]{\textbf{#1}}


\begin{document}
\begin{center}
	\bf
	Algorithms \\
	Computer Science 140 \& Mathematics 168 \\
	Spring 2012 \\
	\rm
	Homework 10a  \\
	Due Thursday, March 29
\end{center}

Please download and read the document ``How to Write a Proof of NP-completeness'' from the course homework webpage.  This provides an example of how to write an NP-completeness proof.

\begin{enumerate}


\item \Points{5} \Name{Professor Lai and NP!}
Professor I. Lai from P.I.T. 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 \Points{30} \Name{Dominating Set.}
	The \textsc{Dominating Set} problem is stated as follows:
	Given a graph $G=(V,E)$ and a positive integer $\ell$, does there exist 
	a subset $S$ of $\ell$ vertices in $V$ such that every vertex in $V$ is
        either in $S$ or is connected by an edge to some vertex in $S$?

	Take a close look at this problem to make sure that you understand how
	this problem differs from the seemingly similar \textsc{Vertex Cover} problem.
	Prove that \textsc{Dominating Set} is NP-complete using a reduction from 3SAT. 
	Write your proof carefully and methodically, using the ``How to Write a Proof of NP-completeness'' document as an example.

\end{enumerate}
\end{document}