\documentclass[12pt]{exam}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage[left=1in, right=1in, top=1in, bottom=1in]{geometry}
\newcommand\Q[1]{\question{\large{\textbf{#1}}}}
\newcommand\modulo{\ \texttt{\%}\ }
\newcommand\lshift{\ \texttt{<<}\ }
\newcommand\rshift{\ \texttt{>>}\ }
\newcommand\cgeq{\ \texttt{>=}\ }
\renewcommand{\H}{\mathrm{H}}
\newcommand{\T}{\mathrm{T}}
\newcommand{\answerbox}[1]{
\begin{framed}
\hspace{5.65in}
\vspace{#1}
\end{framed}}
\newcommand{\trinom}[3]{\begin{pmatrix}#1\\#2\\#3\end{pmatrix}}
\pagestyle{head}
\headrule \header{\textbf{15-251 Assignment 11}}{}{\textbf{Page
\thepage\ of \numpages}}
\pointsinmargin \printanswers
\setlength\answerlinelength{2in} \setlength\answerskip{0.3in}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\N}{\mathbb{N}}
\renewcommand{\P}{\mathsf{P}}
\newcommand{\NP}{\mathsf{NP}}
\begin{document}
\addpoints
\begin{center}
\textbf{\large{15-251 : Great Theoretical Ideas In Computer Science
\\ \vspace{0.2in} Fall 2014
\\ \vspace{0.2in} Assignment 11
}}
\vspace{0.2in}
\large{Due: {\bf Thursday}, December 4, 2014 11:59 PM}
\end{center}
\vspace{0.5in}
\hbox to \textwidth{Name:\enspace\hrulefill}
\vspace{0.2in}
\hbox to \textwidth{Andrew ID:\enspace\hrulefill}
\vspace{0.2in}
% End title box
\vspace{0.5in}
\vspace*{1in}
\begin{center}
\gradetable[h][questions]
\end{center}
\begin{questions}
\setcounter{question}{-1}
\setcounter{numquestions}{-1}
\newpage\Q{Warmup}
\begin{parts}
\part Recall that for a language $L$ to be in NP, we must have a polynomial time ``verifier" that, when given a ``witness'' (proof), can verify that a given $x \in L$. In the case of $\mathit{CIRCUIT\_SAT}$, the proof can simply be a setting of the variables $x_1 \cdots x_n$ such that the circuit evaluates to True, and the verifier can be an algorithm that plugs these values into the circuit and computes the output. \\
What proof and verifier would you provide for the the following languages in NP? \\
$\mathit{3\_SAT}$? \\
$\mathit{3\_COLOR}$? \\
$\mathit{CLIQUE}$? \\
$\mathit{IS\_COMPOSITE}$? \; Checks if an integer $n$ is composite. (This is also in $P$.) \\
$\mathit{TRAVELING\_SALESMAN}$? \; Answers whether a directed graph with weighted edges has a path of cost at most $k$ which visits every vertex exactly once.
\vspace{0.5in}
\part Let $A$ be an NP-Complete problem. \\
Let $B$ be a problem that is poly-time reducible to $A$. That is, we can use an oracle for $A$ to efficiently solve $B$. What can we conclude about $B$? \\
Let $C$ be a problem such that $A$ is poly-time reducible to $C$. That is, we can use an oracle for $C$ to efficiently solve $A$. What can we conclude about $C$? \\
Can $B$ and $C$ be the same problem? Are they necessarily the same problem? Are they in $NP$? Can they be in $P$?
\end{parts}
\newpage
\Q{Getting all snacks}
\begin{parts}
\part[25]
After an exhausting day of grading, the 15-251 TAs visit the cafetaria to grab some
food. The cafeteria serves $m$ different kinds of snacks $S = \{s_i\}_{i=1}^m$. The snacks are grouped into $n$ different types of bags $B_1, \ldots B_n \subseteq
S$ (the same kind of snack might be in multiple bags). That is, each type of bag $B_i$ contains a non-empty subset of the snacks in $S$.
Each bag costs \$1. The 251 TAs want to try all $m$ different kinds of snacks but
Venkat and Victor only give them a budget of $k$ dollars to spend. The problem is
therefore to decide if there are $k$ bags $B_{i_1}, \ldots, B_{i_k}$ such that
$\bigcup_{j=1}^k B_{i_j} = S$.
Show that this problem is NP-Complete. \\
\underline{Hint}: For this homework you may assume that the following problems, as defined in lecture, are NP-Complete: $\mathit{CIRCUIT\-SAT, 3\-SAT, 3\-COLOR, CLIQUE, INDSET}$.
\end{parts}
\newpage
\Q{Those roots can be hard to find}
For a polynomial with integer coefficients in several variables, an
integral root is an assignment of integers to the variables so that
the polynomial evaluates to $0$. For example, the polynomial $2 x_1^2
x_2 - x_1^3 x_2^2$ has an integral root $x_1=2$ and $x_2=1$, where as
the polynomial $x_1^2 + x_2^2 + 1$ has no integral root.
Consider the computational problem of determining, given a polynomial
with integer coefficients, whether it has an integral root. We can
capture this problem by the language:
\begin{align*}
\mathit{ROOT} & = \{\langle p \rangle |\ p
\text{ is a polynomial in several variables, given as a list of its terms,}\\
& \quad \qquad \text{that has an integral root}\} \ .
\end{align*}
In his famous address at the International Congress of Mathematicians
in Paris in 1900, David Hilbert posed 23 mathematical problems as
challenges for the 20th century, the 10'th problem of which, re-stated
in the language of computability theory, was to give a decider for
$\mathit{ROOT}$. We now know, however, that $\mathit{ROOT}$ is in fact
undecidable, so no algorithm exists to tell if a polynomial in several
variables has an integral root.
\begin{parts}
\part[25]
In this problem you are to prove a different property of
$\mathit{ROOT}$, namely, that $\mathit{ROOT}$ is NP-hard.
\underline{Hint}: How can you enforce a potential integral root to only take values in $\{0,1\}$? One possible reduction is from $\mathit{3\-SAT}$ (though, again, you may reduce from any of $\mathit{CIRCUITSAT, 3\-SAT, 3\-COLOR, CLIQUE, INDSET}$, or even some new intermediate problem that you prove to be NP-complete).
\end{parts}
\newpage
\Q{What's the smallest circuit?}
\begin{parts}
\part[25]
Let {\sc SmallestCircuit} be the language consisting of (suitable encodings in $\{0,1\}^\ast$) of all Boolean circuits $C$ (with many input bits and a single output bit) with the property that there is no smaller circuit $C'$ that has the same truth table as $C$. (Here ``smaller" means fewer gates, and the truth table of a circuit with $n$ inputs has $2^n$ entries, one for each setting of the $n$ input bits.)
Prove that if $\P = \NP$, then {\sc SmallestCircuit} $\in \P$.
\underline{Hint}: If a language is in $\P$, then its complement is also in $\P$. Also, think about how you would check whether two circuits, each with $n$ inputs, compute the same truth table.
\end{parts}
\newpage\Q{Balanced gifting}
It is the holiday season now, and you have a collection of $n$ awesome gifts, the $i$'th gift being worth $v_i$ dollars, to be distributed among $m$ of your family members (assume $n > m$, so you have enough gifts for everyone).
You want to give away all the gifts, each gift going to exactly one person (the gifts are indivisible). However, the value $v_i$ of the gifts is public knowledge, so everyone will know the total value everyone else receives. So to minimize envy, you would like to allocate the gifts in a balanced way, so as to minimize the maximum value any person receives.
Formally, you would like to find a partition $\mathcal{P}$ of the $n$ gifts as $\{1,2,\dots,n\}=S_1 \cup S_2 \cup \cdots \cup S_m$, the $S_j$'s being disjoint sets with the $j$'th person receiving the gifts in subset $S_j$, so that
\begin{equation}
\label{eq:sol-val}
V(\mathcal{P}) \stackrel{def}{=}
\max_{j \in \{1,2,\dots,m\}} \sum_{i \in S_j} v_i
\end{equation}
is {\em minimized}.
Let $\mathsf{OPT}$ be the minimum value of $V(\mathcal{P})$ over all possible partitions $\mathcal{P}$.
Turns out finding the optimal partition $\mathcal{P}$ with $V(\mathcal{P}) = \mathsf{OPT}$ is a hard problem. It is in fact one of those pesky NP-hard problems you know about. However, you also know something about how to cope with NP-hard problems by finding approximately optimal solutions.
\begin{parts}
\part[25]
Can you show off your 15-251 skills this holiday season by designing an efficient algorithm, running in time polynomial in $n$, that finds a partition $\mathcal{P}$ with $V(\mathcal{P}) \le 2 \cdot \mathsf{OPT}$?
%with solution value given in Eq. \eqref{eq:sol-val} that is at most $2$ times bigger than the minimum possible value of the quantity \eqref{eq:sol-val} over all allocations?
\underline{Hint}: One approach is to use an appropriate ``greedy" strategy. Also, think about how to lower bound $\mathsf{OPT}$ in terms of the $v_i$'s and $m$.
\end{parts}
\end{questions}
\end{document}