News for hackers. Stuff that matters.
Re:P versus NP Explained by peeters on Monday February 03, 2014 @10:21AM (#7171027)
The terminology in the text misses the mark a bit.

- P and NP are not disjoint sets. NP just means "verifiable in polynomial time." There are plenty of easy problems to solve that are verifiable in polynomial time. P is in fact a subset of NP.

- NP-hard problems are ones that are difficult for computers to solve

- NP-complete is the intersection between NP-hard and NP

Furthermore, it presents the P vs NP problem as an attempt by mathematicians to solve P = NP, whereas almost no mathematicians believe P = NP, they're just all trying to prove that P != NP.

Re:P versus NP Explained by danielrm26 on Monday February 03, 2014 @10:27AM (#7171051)
Apologies. I was trying to keep it as simple as possible. I don't think people who need to know it to that degree will even need the summary I provided.
Re:P versus NP Explained by peeters on Monday February 03, 2014 @10:27AM (#7171055)
I think keeping it simple is great, but you should bring your terminology in the text to be consistent with the diagram at the start, otherwise it's confusing.

I don't think it would be difficult to say something like:

> P and NP are two different kinds of problems. P problems are easy for computers to solve, and NP problems are easy for computers to check answers for. All P problems are NP problems; that is, if it's easy for the computer to solve, it's easy to verify the solution. The P vs NP problem asks: within the class of NP problems, are there problems which are not P, that is, which are not easy for computers to solve?

Re:P versus NP Explained by parfitt on Monday February 03, 2014 @04:11PM (#7173517)
Thank you. That is a wonderful description of what the P vs NP problem is all about.
Re:P versus NP Explained by danielrm26 on Monday February 03, 2014 @10:33AM (#7171096)
Can I use that?
Re:P versus NP Explained by peeters on Monday February 03, 2014 @10:38AM (#7171124)
By all means.
Re:P versus NP Explained by danielrm26 on Monday February 03, 2014 @10:49AM (#7171202)
Updated. Thanks for the input.