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.
[ Parent
| on HN ]
There are no comments on this comment yet.