There is no known polynomial-time algorithm for set cover.
Even more striking, the problem is NP-complete. This means that, unless P = NP, there is no polynomial-time algorithm for set cover.
We'll prove this shortly. NP-complete = in NP + NP-hard. Argue that it is in NP. We'll do hardness shortly.
