You're sitting at your desk one day when a FedEx package arrives for you. Inside is a...

You're sitting at your desk one day when a FedEx package arrives for you. Inside is a cell phone that begins to ring, and you re not entirely surprised to discover that it s your friend Neo, whom you haven t heard from in quite a while. Conversations with Neo all seem to go the same way: He starts out with some big melodramatic justification for why he s calling, but in the end it always comes down to him trying to get you to volunteer your time to help with some problem he needs to solve.

This time, for reasons he can t go into (something having to do with protecting an underground city from killer robot probes), he and a few associates need to monitor radio signals at various points on the electromagnetic spectrum. Specifically, there are n different frequencies that need monitoring, and to do this they have available a collection of sensors.

There are two components to the monitoring problem.

• A set L of m geographic locations at which sensors can be placed; and

• A set S of b interference sources, each of which blocks certain frequencies at certain locations. Specifically, each interference source i is specified by a pair (Fi, Li), where Fi is a subset of the frequencies and Li is a subset of the locations; it signifies that (due to radio interference) a sensor placed at any location in the set Li will not be able to receive signals on any frequency in the set Fi.

We say that a subset L c L of locations is sufficient if, for each of the n frequencies j, there is some location in L where frequency j is not blocked by any interference source. Thus, by placing a sensor at each location in a sufficient set, you can successfully monitor each of the n frequencies.

They have k sensors, and hence they want to know whether there is a sufficient set of locations of size at most k. We ll call this an instance of the Nearby Electromagnetic Observation Problem: Given frequencies, locations, interference sources, and a parameter k, is there a sufficient set of size at most k?

Example. Suppose we have four frequencies {f1, f2, f3, f4} and four locations l2, l3, l4}. There are three interference sources, with

Then there is a sufficient set of size 2: We can choose locations l£2 and l£4 (since f1 and f2 are not blocked at l4, and f3 and f4 are not blocked at l2).

Prove that Nearby Electromagnetic Observation is NP-complete.