# choose minimum number of M professors in polynomial time in order to design all N course exams

Think that we have M professors and N courses every professor can wrote question for at least one course exam. we want to choose minimum number of professors in order to design question for all N courses exams.

I try to hard but I only could model this question in a bipartite graph that one sections are professors and the other sections includes courses every professors are connected to every courses that they can design question for them.

we wish to choose minimum professors to cover all courses. one easy method is to check all cases and pick the minimum one in exponentioal time order...

could any one help me to solve it in polynomial time?

thanks

• You can't solve it in polynomial time. Read about the "Set Cover" problem. – Mihai May 20 '16 at 9:21
• Check this. – hengxin May 20 '16 at 9:26

Reduction: Take All courses as a Universal set U which you want to cover. Then make collection of sets $S=\{P_1,P_2,...,P_m\}$ where, $P_i$ is the set of subjects for which a professor $i$ can design a question. and you can go similarly in reverse direction.