Talk:Karp's 21 NP-complete problems
[edit] 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)
[edit] 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)
