News for hackers. Stuff that matters.
Re:The polynomial algorithm for 3-SAT problem (or P=NP) by kd0amg on Thursday January 20, 2011 @01:39AM (#2122909)
The NP-complete problems are a subset of NP ("nondeterministic polynomial") problems, specifically those to which all NP problems are polynomial-time reducible. They are, in essence, the hardest problems in class NP. It's pretty trivial to show that integer factoring is in NP; what's not known is whether it's NP-complete. If any NP-complete problem is in P, then via polynomial-time reduction, all problems in NP are in P.

There are no comments on this comment yet.