Suppose you’re to organize a summer sports camp, and the
following problem comes up. the camp is supposed to have at least
506

one counselor who’s skilled at each of the n sports covered by the camp
(baseball, volleyball, and so on). they have received job applications from
m potential counselors. for each of the n sports, there is some subset
of the m applicants qualified in that sport. the question is: for a given
number k < m, is it possible to hire at most k of the counselors and have
at least one counselor qualified in each of the n sports? we’ll call this the
efficient recruiting problem.
show that efficient recruiting is np-complete.