[prtk]

Rating 3/10. I don't think this article is written by someone who knows the topic well.

e.g. you don't too complicated math as claimed in this line:

>> It is known that all P problems are NP problems; the proof requires math which is too complicated for this article but may be explained in the future.

For P problems can be solved easily and then the solution can be easily verified. This means all P problems are NP problems too.

Good news!! Better Article Exists. Read: http://cstheory.stackexchange.com/questions/5188/explain-p-n...

[MarkPNeyer]

I would agree that the math required is not 'complicated' from the point of view of anyone with basic understanding of discrete logic, but it's certainly too complicated to express in simple english terms that are understandable at the level i was shooting for.

if you want to do the proof that all problems in P are also in NP, you have to explain the notion of a decision problem and show that any np-complete numerical optimization problem can be converted to a decision problem without increasing its computational complexity by more than a function bounded by a polynomial.

someone named 'balabiot' changed the article by adding an incorrect 'proof' that P is a subset of NP, at the same time you made this post. the incorrect proof reads:

  All P problems are NP problems: if a problem is easy to 
  solve, to check an answer you just solve it and check that 
  the results match.

this invalid proof makes the assumption that an np-complete problem has a single solution. many np-complete problems have multiple solutions; there many be many ways to pack the knapsack, color the graph, or satisfy the boolean circuit. if you are presented with a valid solution, but the algorithm you use to solve the problem instance produces a different, but also valid solution, your comparison would fail.

note that simply solving the problem (because it is in p) is NOT the same thing as verifying a solution correct.