Talk:Karp's 21 NP-complete problems

Latest comment: 2 years ago by Madvorak in topic Hitting set

Approximability edit

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)Reply

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)Reply

The concept NP-completeness is an error edit

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=%22Juan%20Manuel%20Dato%22

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)Reply

Seiner tree link incorrect edit

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)Reply

Hitting set edit

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 (talkcontribs) 17:00, 19 January 2022 (UTC)Reply