Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
Philip, I don't understand what's bothering you. Very roughly, and I'm annoyed that Wikipedia gives such an imprecise definition, a problem which is NP but not P has no simple method for finding an answer, but once a proposed answer is found, it is easy to check whether that answer is correct. –  Grumpy Parsnip Sep 15 '11 at 22:37
4  
@Jim It's a "simple english wikipedia" page. :) –  Srivatsan Sep 16 '11 at 0:00
add comment

1 Answer

up vote 8 down vote accepted

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$).

share|improve this answer
5  
@Philip In particular, the abbreviation NP does not stand for non-polynomial. :-) –  Srivatsan Sep 15 '11 at 23:05
    
@mixedmath: Thanks -- yeah, the example wasn't very clear on whether it's difficult to find a division method. –  Phillip Sep 16 '11 at 15:30
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.