% -*- compile-command: "rubber -d --unsafe hw-11-NP.tex" -*-
\documentclass[11pt]{tufte-handout}
\usepackage[num=11,date=December\ 6,topic=NP]{algorithms-hw}
\begin{document}
\coversheet
\begin{question}
Consider the following three variant problems:
\begin{itemize}
\item \textsc{Independent-Set}: Given a graph $G$ and an integer
$k \geq 0$ as input, does $G$ have an independent set of size $k$?
(This is a so-called \emph{decision problem}, which outputs a
single bit, \emph{i.e.} a True/False value.)
\item \textsc{Max-Independent-Set}: Given a graph $G$ as input,
output the largest $k$ such that $G$ has an independent set of
size $k$.
\item \textsc{Find-Max-Independent-Set}: Given a graph $G$ as input,
output a subset of vertices of $G$ which is a maximum-size
independent set.
\end{itemize}
Intuitively these are ordered from least to most informative:
\textsc{Independent-Set} outputs just a boolean;
\textsc{Max-Independent-Set} outputs a value $k$; and
\textsc{Find-Max-Independent-Set} outputs an actual maximum
independent set.
\begin{enumerate}[label=(\alph*)]
\item Prove that \[ \textsc{Independent-Set} \leq_P
\textsc{Max-Independent-Set} \leq_P
\textsc{Find-Max-Independent-Set}. \]
\item Prove that
$\textsc{Max-Independent-Set} \leq_P \textsc{Independent-Set}$.
\marginnote{\emph{Hint}: you can use the \textsc{Independent-Set}
black box more than once, as long as you only use it a
polynomial number of times.}
\item Prove that $\textsc{Find-Max-Independent-Set} \leq_P \textsc{Independent-Set}$.
\end{enumerate}
We will often restrict ourselves to studying \emph{decision
problems} (which have a simple True/False answer) since they are
much simpler to work with but tend to be ``just as hard as'' other
variants which return more informative answers.
\end{question}
\begin{question}[K\&T 8.4] \label{q:resource}
Suppose you're consulting for a group that manages a
high-performance real-time system in which asynchronous processes
make use of shared resources. Thus the system has a set of $n$
\emph{processes} and a set of $m$ \emph{resources}. Each process
specifies a set of resources that it requests to use. Each resource
might be requested by many processes; but it can only be
used by a single process. Your job is to allocate resources to
processes that request them. If a process is allocated all the
resources it requests, then it is \emph{active}; otherwise it is
\term{blocked}. You want to perform the allocation so that as many
processes as possible are active. Thus we phrase the
\textsc{Resource Reservation} problem as follows: Given a set of
processes and resources, the set of requested resources for each
process, and a number $k$, is it possible to allocate resources to
processes so that at least $k$ processes will be active?
Consider the following list of problems. For each problem either
give a polynomial-time algorithm or prove that the problem is
NP-complete. \marginnote[-5em]{Remember that to show a problem is
NP-complete, you must show \emph{two} things: that the problem is
in NP, and that it is NP-hard. Remember that a problem $X$ is
NP-hard if there is some other NP-hard problem $H$ with a
polynomial reduction $H \leq_P X$. Be sure to get this the right
way around! You may assume that \textsc{SAT}, \textsc{3-SAT},
\textsc{Independent-Set}, \textsc{Vertex-Cover}, and
\textsc{Set-Cover} are all NP-hard.}
\begin{enumerate}[label=(\alph*)]
\item The general \textsc{Resource Reservation} problem defined
above.
\item The special case of the problem when $k = 2$.
\item The special case of the problem when there are two types of
resources---say, people and equipment---and each process requires
at most one resource of each type. (In other words, each process
requires at most one specific person and one specific piece of
equipment.)
\item The special case of the problem when each resource is
requested by at most two processes.
\end{enumerate}
\end{question}
% \begin{question}[K\&T 8.5]
% Consider a set $A = \{a_1, \dots, a_n\}$ and a collection $B_1,
% B_2, \dots, B_m$ of subsets of $A$ (\ie, $B_i \subseteq A$ for
% each $i$).
% We say that a set $H \subseteq A$ is a \term{hitting set} for the
% collection $B_1, B_2, \dots, B_m$ if $H$ contains at least one
% element from each $B_i$---that is, if $H \cap B_i$ is not empty for
% each $i$ (so $H$ ``hits'' all the sets $B_i$).
% We now define the \textsc{Hitting Set} problem as follows. We are
% given a set $A = \{a_1, \dots, a_n\}$, a collection
% $B_1, B_2, \dots, B_m$ of subsets of $A$, and a number $k$. We are
% asked: Is there a hitting set $H \subseteq A$ for
% $B_1, B_2, \dots, B_m$ whose size is at most $k$?
% Prove that \textsc{Hitting Set} is NP-complete.
% \end{question}
% \begin{question}[K\&T 8.6] Consider an instance of the
% \textsc{Satisfiability} problem, specified by clauses $C_1, \dots,
% C_k$ over a set of Boolean variables $x_1, \dots, x_n$. We say that
% the instance is \term{monotone} if each term in each clause consists
% of a nonnegated variable; that is, each term is equal to $x_i$, for
% some $i$, rather than $\overline{x_i}$. Monotone instances of
% \textsc{Satisfiability} are very easy to solve: they are always
% satisfiable, by setting each variable equal to $1$.
% For example, suppose we have the three clauses \[ (x_1 \lor x_2),
% (x_1 \lor x_3), (x_2 \lor x_3). \] This is monotone, and indeed the
% assignment that sets all three variables to $1$ satisfies all the
% clauses. But we can observe that this is not the only satisfying
% assignment: we could also have set $x_1$ and $x_2$ to $1$, and $x_3$
% to $0$. Indeed, for any monotone instance, it is natural to ask how \emph{few}
% variables we must set to $1$ in order to satisfy it.
% Given a monotone instance of \textsc{Satisfiability}, together with
% a number $k$, the \emph{Monotone Satisfiability with Few True
% Variables} problem asks: is there a satisfying assignment for the
% instance in which at most $k$ variables are set to $1$? Prove that
% this problem is NP-complete.
% \end{question}
\begin{question}
The \textsc{Subset Sum} problem asks, given as inputs a set of
integers $\{x_1, \dots, x_n\}$ and a target sum $S$, is there a
subset of the $x_i$ whose sum is exactly $S$? It turns out that this
problem is NP-complete.\footnote{This can be proved by reduction
from 3-SAT, but you don't need to understand the proof to answer
this question.} On an activity in class, you actually wrote a
dynamic programming algorithm to solve this problem. Explain why
you do not win \$1 million.
\end{question}
\end{document}