Talk:Karp's 21 NP-complete problems

Approximability

I thought that MAX-CUT could be easily approximated to within a factor of 2 (and also within a factor of 1/0.8... using semi-definite programming). How can a special case not be approximable within any constant factor? LachlanA (talk) 19:06, 21 February 2008 (UTC)

Look at the cited paper. The standard optimization problem is approximable, but it has another optimization version that is not. Dcoetzee 19:13, 21 February 2008 (UTC)

The concept NP-completeness is an error

I wrote an explanation in Spanish which demonstrates the concept "completeness" is a wrong. I'll translate it as soon as possible in that site.

http://www.archive.org/search.php?query="Juan Manuel Dato"

You could demonstrate that SAT is in P and that NP is not always P. In example, Cook's Theorem says in his demonstration that every NP problem could be expressed in logic of first order; if it is true, Gödel demonstrated the completeness of the first order, so every NP problem could be solved in a time. But the Principia Mathematica is not complete, thinking in the validity of a formula we can waste an exponential time to discover that kind of problem (we can call it NE) could be expressed using the Theorem of Cook like in logic of first order because Cook never used the limitation of polynomial time by its expresion. Therefore, that is impossible.

But we can find other reasons why the Theorem of Cook cannot be used. —Preceding unsigned comment added by 95.39.137.21 (talk) 09:26, 2 March 2011 (UTC)

Seiner tree link incorrect

The Steiner tree referred to in Karp is more properly called the graph Steiner tree, i.e. a minimum weight tree that spans a given subset of the vertices of a graph. This is analogous to geometric Steiner trees which was the link target, but not the same. I'm repointing the link, but I think ideally we would have more info on this problem. RDBury (talk) 22:00, 9 August 2013 (UTC)

Hitting set

Karp defined the Hitting set problem as follows.

INPUT: family {U_i} of subsets of [r]. PROPERTY: There is a set W such that, for each i, |W \cap U_i| = 1.

However, the link here refers to a definition (weaker) that |W \cap U_i| is non-empty. Hence the "wikipedia definition" of the Hitting set problem is trivially equivalent to the Set cover problem; which is not the case for Karp's problems. — Preceding unsigned comment added by Madvorak (talk • contribs) 17:00, 19 January 2022 (UTC)