This is a practice problem from my algorithms class. (And no, it was not assigned as homework. I can't prove this, but you don't have to answer if you don't believe me.) To me this seems like a very difficult problem to show NP-completeness for since due to its abundance of features, it's tricky to mold a known NP-complete problem into it.
You’ve been asked to organize a freshman-level seminar. The plan is to have the first portion of the semester consist of a sequence of $l$ guest lectures by outside speakers, and have the second portion of the semester devoted to a sequence of $p$ hands-on projects that the students will do. There are $n$ options for speakers overall, and in week number $i$ (for $i = 1, 2, \ldots, l$) a subset $L_i$ of these speakers is available to give a lecture. On the other hand, each project requires that the students have seen certain background material in order for them to be able to complete the project successfully. In particular, for each project $j$ (for $j = 1, 2, \ldots , p$), there is a subset $P_j$ of relevant speakers so that the students need to have seen a lecture by at least one of the speakers in the set $P_j$ in order to be able to complete the project. So this is the problem: Given these sets, can you select exactly one speaker for each of the first $l$ weeks of the seminar, so that you only choose speakers who are available in their designated week, and so that for each project $j$, the students will have seen at least one of the speakers in the relevant set $P_j$. We’ll call this the Lecture Planning Problem. Prove that Lecture Planning is NP-complete.
I should note that it isn't explicitly stated in the problem, but I'm assuming that a speaker can only give at most one talk. (But if this seems to prevent the problem from being NP-complete, let me know.)
At first I tried solving some graph-based problems (e.g., Independent Set) using Lecture Planning, but wasn't able to proceed because I'm not sure how you would partition vertices into subsets $L_i$ or $P_j$.
Thus I decided to go to 3-SAT. Even then, it is not obvious how you would solve 3-SAT using this setup. E.g., what would the clauses be? My first thought was they could be the $l$ subsets $L_i$, and you would need a variable to be true in each; this would correspond to picking a speaker for that week. But then how do you incorporate the $P_j$ so as to ensure the formula is satisfied (if satisfiable)?
Also thought about making the clauses the $P_j$, but again, this didn't really seem to work.
I would greatly appreciate a hint. Thanks!
