Note: Include your Cornell NetID on your each section of your homework. This simplifies the process of recording your grades.
Note: Prelim II takes place Tuesday, April 12, at 7:30pm.
Consider an instance of the Satisfiability problem, specified by clauses C1, ..., Ck over a set of Boolean variables x1, ..., xn. We say that the instance is monotone if each term in each clause consists of a non-negated variable; that is, each term is equal to xi, for some i, rather than not(xi). Monotone instances of 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
(x1 or x2), (x1 or x3),
(x2 or x3).
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 x1 and x2
to 1, and x3 to 0. Indeed, for any monotone instance, it is
natural to ask how few variables we need to set to 1 in order to satisfy it.
Given a monotone instance of Satisfiability, together with a number k, the problem of Monotone Satisfiability with Few True Variables asks: is there a satisfying assignment for the instance in which at most k variables are set to 1? Prove this problem is NP-complete.
You're configuring a large network of workstations, which we'll model as an undirected graph G --- the nodes of G represent individual workstations and the edges represent direct communication links. The workstations all need access to a common core database, which contains data necessary for basic operating system functions.
You could replicate this database on each workstation --- then lookups would be very fast from any workstation, but you'd have to manage a huge number of copies. Alternately, you could keep a single copy of the database on one workstation and have the remaining workstations issue requests for data over the network G; but this could result in large delays for a workstation that's many hops away from the site of the database.
So you decide to look for the following compromise: you want to maintain a small number of copies, but place them so that any workstation either has a copy of the database, or is connected by a direct link to a workstation that has a copy of the database.
Thus, we phrase the Server Placement problem as follows: Given the network G, and a number k, is there a way to place k copies of the database at k different workstations so that every workstation either has a copy of the database, or is connected by a direct link to a workstation that has a copy of the database?
Show that Server Placement is NP-complete.
There are those who insist that the initial working title for Episode XXVII of the Star Wars series was P = NP --- but this is surely apocryphal. In any case, if you're so inclined, it's easy to find NP-complete problems lurking just below the surface of the original Star Wars movies.
Consider the problem faced by Luke, Leia, and friends as they tried to make their way from the Death Star back to the hidden Rebel base. We can view the galaxy as an undirected graph G = (V,E), where each node is a star system and an edge (u,v) indicates that one can travel directly from u to v. The Death Star is represented by a node s, the hidden Rebel base by a node t. Certain edges in this graph represent longer distances than others; thus, each edge e has an integer length le > 0. Also, certain edges represent routes that are more heavily patrolled by evil Imperial spacecraft; so each edge e also has an integer risk re > 0, indicating the expected amount of damage incurred from special-effects-intensive space battles if one traverses this edge.
It would be safest to travel through the outer rim of the galaxy, from one quiet upstate star system to another; but then one's ship would run out of fuel long before getting to its destination. Alternately, it would be quickest to plunge through the cosmopolitan core of the galaxy; but then there would be far too many Imperial spacecraft to deal with. In general, for any path P from s to t, we can define its total length to be the sum of the lengths of all its edges; and we can define its total risk to be the sum of the risks of all its edges.
So Luke, Leia, and company are looking at a complex type of shortest-path problem in this graph: they need to get from s to t along a path whose total length and total risk are both reasonably small. In concrete terms, we can phrase the Galactic Shortest Path problem as follows: given a set-up as above, and integer bounds L and R, is there a path from s to t whose total length is at most L, and whose total risk is at most R?
Prove that Galactic Shortest Path is NP-complete.