5
$\begingroup$

I'm reading the page under http://simple.wikipedia.org/wiki/P_versus_NP, which states:

"...people want to know if there are any NP problems that are not P problems. That means they would like to know if there are any problems where the answer cannot easily be found by a computer, but if someone says he has the answer, it is easy to use a computer to check if that answer is correct."

Don't the included examples show this? Example 1, for instance, states:

However, if she proposed a division of the rocks, it would be trivial to check if she was right. All you would need to do would be to check if the sum of the weights in each pile were equal, which is easy for a computer to do, even for this large number.

Doesn't this show that the method for finding a correct division of rocks is difficult to compute but easy to verify?

  • 4
    @Jim It's a "simple english wikipedia" page. :)2011-09-16

1 Answers 1

8

No, it simply says that it is easy to verify. Is it difficult to compute? Maybe. It might be. We certainly aren't very good at computing it right now, but we haven't proven that it is hard to compute yet (hard in the sense that $P \neq NP$).

  • 0
    @mixedmath: Thanks -- yeah, the example wasn't very clear $o$n wh$e$ther it's difficult to find a division $m$ethod.2011-09-16