CSC373 Assignment 4

CSC373
Assignment 4

Instructions
1. Typed assignments are preferred (e.g., PDFs created using LaTeX or Word), especially if
your handwriting is possibly illegible or if you do not have access to a good quality scanner.
Either way, you need to submit a single PDF named “hwk4.pdf” on MarkUS at https:
//markus.teach.cs.toronto.edu/2022-05
2. You will receive 20% of the points for a (sub)question when you leave it blank (or cross o↵
any written solution) and write “I do not know how to approach this problem.” If you leave
it blank but do not write this or a similar statement, you will receive 10%. This does not
apply to any bonus (sub)questions.
3. You may receive partial credit for the work that is clearly on the right track. But if your
answer is largely irrelevant, you will receive 0 points.
Q1 [15 Points] Complement of an NP Problem
For a decision problem D0, define D0 to be its complement problem i.e., a YES instance of D0 is
a NO instance of D0 and a NO instance of D0 is a YES instance of D0. Below, “K” denotes a
Karp reduction as defined in class (i.e., a polynomial time reduction that only produces a single
instance and preserves the YES/NO value).
(a) [7.5 Points] Give a decision problem D0 such that D0 K D0.
Define D0 precisely, describe the reduction D0 K D0 in detail, and prove that your reduction is
correct.
(b) [2.5 Points] Does your decision problem D0 from part (a) belong to NP? Justify.
(c) [5 Points] Suppose that D1 is a decision problem such that D1 p D1 and D1 is NP-complete.
What can you conclude? Make the strongest claim you can and prove it.
Q2 [15 Points] Exponential Algorithms for NP Problems
Show that for every decision problem D 2 NP, there is some polynomial p(n) and some algorithm
A (both of which depend on D) such that A solves D in worst-case time O

2p(n)

.
Hint: This involves mostly “unrolling” the definitions, so write up your answer carefully. In your
answer, you must use the formal definition of NP in terms of polynomial-time verifiers – for this,
you can refer to class slides or page 1064 of the text.
Q3 [20 Points] Showing NP-Completeness I
A web server has a number of simultaneous “requests” to reply to. The server has to send its replies
in “packets,” each one of which has a fixed positive integer size limit L. Each packet can contain
1
more than one reply (so multiple requests can be replied to in a single packet), but each individual
reply has its own positive integer size si. We would like to use as few packets as possible to send
all of the replies.
This problem can be formulated formally as a decision problem FewPackets (“FP” for short),
as follows:
Input: Positive integer packet size limit L, positive integers reply sizes s1,...,sn, positive integer
number of packets k.
Output: Is there some partition of {1,...,n} into packets P1,...,Pk, where each packet has size at
most L– formally: 9P1,...,Pk, P1[· · ·[Pk = {1,...,n}^(8i, j, Pi\Pj = ;)^8i,P
j2Pi sj  L?
For example, (8, {2, 5, 4, 5}, 3) 2 FP because we can use packets P1 = {1, 3} (with size s1 + s3 =
2+4  8), P2 = {2} (with size s2 = 5  8), and P3 = {4} (with size s4 = 5  8). However,
(8, {2, 5, 4, 5}, 2) 2/ FP because there is no way to partition every reply into only 2 packets, each
one of size  8 – even though the total size of all replies is only 16.
Write a detailed proof that FP is NP-complete: first show that FP 2 NP, and then use a reduction
from Subset-Sum to show that FP is NP-hard. You may assume that the following “positive
integer” version of Subset-Sum is NP-complete:
Input: Positive integer W (target sum) and a set S of n positive integers {x1,...,xn}.
Output: Is there some subset ; 6= S0 ✓ S that sums to exactly W?
Q4 [20 Points] Showing NP-Completeness II
Imagine that we have a network of processors, each one of which needs access to a common database
in order to carry out its work (for example, a network of banking machines accessing client information). To simplify, assume all operations are queries (no operation changes the data). Our
problem is to determine which processor(s) should store the database (these processors will be
called “servers”) in order to have reasonably fast access time (including the load on each server),
as well as having as little duplication of the database as possible.
At one extreme, each processor could store its own copy of the database. This would ensure the
fastest possible access time, but at the cost of replicating the database many times. At the other
extreme, the database could be stored in a single server (all other processors would connect to the
server to access the data). This would ensure the smallest amount of duplication, but at the cost
of longer access times and server load. In either case, there is a significant cost if the network is
large.
A reasonable middle ground between the two extremes would be to fix a distance parameter d and
to store the database on as few servers as possible, chosen so that every processor is within distance
d of at least one server (the distance is measured as the minimum number of links required to send
communications from one processor to the next). Unfortunately, it seems impossible to solve this
problem eciently.
Formally, show that the following ServerLocation problem is NP-complete. You may use any
NP-complete problem from class for your reduction.
Input: An undirected graph G (the network of processors) and non-negative integers k and d.
2
Output: Is there some subset S of no more than k vertices (the “servers”) such that every processor
is within distance d of some server in S? (The “distance” between vertices u, v is measured
as the number of edges on a shortest path from u to v, or infinity (1) if there is no path
from u to v.)
3