News for hackers. Stuff that matters.
Re:P versus NP Explained by _greim_ on Monday February 03, 2014 @02:00PM (#7172712)
> P problems are easy for computers to solve, and NP problems are easy for computers to check answers for, but extremely difficult for computers to solve. [...] All P problems are NP problems

Seems like a direct contradiction. Typo, or am I missing something?

Re:P versus NP Explained by 14113 on Monday February 03, 2014 @02:08PM (#7172760)
Sort of - we don't know if NP problems are hard for computers to solve, that's really the whole question!

Technically, P is a subset of NP. Problems in NP have answers (called certificates) which can be verified, or checked, using an algorithm that runs in polynomial time (that is asymptotically O(n^x), where X is a finite integer). Problems that are in P are those that have a polynomial time algorithm to construct an answer.

Any problem that's in P is therefore in NP, as we can simply run the algorithm for constructing the answer then compare it with the certificate to see if they match.

P vs NP simply asks if all problems in NP can be solved in polynomial time, hence P=NP.

Re:P versus NP Explained by _greim_ on Monday February 03, 2014 @02:19PM (#7172821)
Ahh. Thank you. This actually makes more sense than the article itself!
Re:P versus NP Explained by tanderson11 on Monday February 03, 2014 @02:07PM (#7172752)
All P problems are in NP. If you can solve a problem in polynomial time, you could simply "check" the problem on an input by solving the problem and seeing if the test input were in the set of solutions. It will clearly take P time to perform that "check" (because you can solve the problem in P time). This means all problem in P must be in NP.

The error is that not all problems in NP are "extremely difficult for computers to solve". The difficulty of solving problems in NP varies drastically between particular problems.

Re:P versus NP Explained by peeters on Monday February 03, 2014 @03:02PM (#7173076)
This is coming from my suggestion above, but in my suggestion, I omitted "but extremely difficult for computers to solve", leaving it with:

> P problems are easy for computers to solve, and NP problems are easy for computers to check answers for.

The problem is the text still uses "NP problems" and "NP complete problems" interchangeably, when it shouldn't. (The diagram at the top gets it right!)

Re:P versus NP Explained by sherjilozair on Monday February 03, 2014 @02:13PM (#7172778)
If you can solve something easily, then you can also verify its solutions easily.

It is a typo. It should say "but potentially extremely difficult for computers to solve."