Re:The polynomial algorithm for 3-SAT problem (or P=NP)
by sonoffett on Wednesday January 19, 2011 @11:43PM
(#2122675)
Cperciva is right, but I think you're mistaken when you say "many problems harder than NP are NP complete", NP complete problems are both NP and NP hard. NP hard is a class of problems such that every problem in NP can be reduced to any problem in NP hard. Meaning if P=NP then every problem in NP(including the NP complete problems) can be solved in polynomial time; all it takes is one algorithm that solves an NP complete problem in polynomial time (note that this does not show that P=NP hard, a much stronger claim).
[ Parent
| on HN ]