News for hackers. Stuff that matters.
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).
Re:The polynomial algorithm for 3-SAT problem (or P=NP) by bdr on Thursday January 20, 2011 @12:14AM (#2122747)
You're right. I've got the brain hiccups.