Talk:Set cover problem

From Wikipedia, the free encyclopedia

What does it mean to call the decision problem NP-complete and the optimization problem NP-hard? NP-hardness refers to decision problems. Isn't #P-completeness the notion we are after for the optimization part?

NP-Complete means that the problem is both NP-Hard (harder than any other problem in NP) as well as in NP (meaning a given solution can be verified in polynomial time). We can verify that a solution to the decision problem is valid in polynomial time (by simply checking if there are at most k sets used in the solution, and whether those sets actually do cover U). However, it is more difficult to verify a solution to the optimization problem, as we have to check whether the given solution is in fact the optimal one (which can't be done in polynomial time). This means the optimization problem is not in NP, and therefore cannot be NP-Complete. So no, NP-hardness does not always refer to decision problems. —Preceding unsigned comment added by 128.113.55.43 (talk) 02:45, 22 April 2008 (UTC)

NP is a class of decision problems, so an optimization problem cannot be in NP *by definition*. Your argument is a red herring (in particular since it is probably difficult to prove that deciding whether a given solution is optimal cannot be done in polynomial time). --Mellum (talk) 12:35, 12 May 2008 (UTC)