Talk:Set cover problem
|WikiProject Computer science||(Rated C-class, Mid-importance)|
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 188.8.131.52 (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)
I believe that set packing and hitting set are duals of one another, not set cover and hitting set, as indicated in "related problems." Set cover and hitting set are both minimization problems. —Preceding unsigned comment added by 184.108.40.206 (talk) 16:12, 4 September 2008 (UTC)
- True. I corrected that and added a template Template:Covering-Packing_Problem_Pairs with the goal to collect all important covering problems together with their LP-dual problems. ylloh (talk) 17:50, 11 March 2009 (UTC)
Hitting set and set cover
m and n
Hi everyone, There is a mistake in this article: the universe should contain n elements instead of m, and the collection of subsets should be of size m instead of n. This way, the approximability and inapproximability section become correct. — Preceding unsigned comment added by 220.127.116.11 (talk) 20:56, 8 May 2012 (UTC)
The decision version of set covering is NP-complete, and the optimization version of set cover is NP-hard.