% -*- 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}
