Talk:Karp's 21 NP-complete problems

This article is within the scope of WikiProject Computer science, a collaborative effort to improve the coverage of Computer science related articles on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.Computer scienceWikipedia:WikiProject Computer scienceTemplate:WikiProject Computer scienceComputer science

Low

This article has been rated as Low-importance on the project's importance scale.

Things you can help WikiProject Computer science with:

Here are some tasks awaiting attention:

Article requests :
- Requested articles/Applied arts and sciences/Computer science, computing, and Internet
Cleanup :
- Computer science articles needing attention
- Computer science articles needing expert attention
Copyedit :
- Computing
Expand :
- Computer science
Infobox :
- Computer science articles without infoboxes
Maintain :
- Timeline of computing 2020–present
Photo :
- Find pictures for the biographies of computer scientists (see List of computer scientists)
- Computing articles needing images
Stubs :
- Computer science stubs
Unreferenced :
- WikiProject Computer science/Unreferenced BLPs
Project-related :
- Tag all relevant articles in Category:Computer science and sub-categories with {{WikiProject Computer science}}

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

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

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

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)[reply]