I add a look at the partition problem, this problem is know as the Easiest hard problem since it is NP-complete and seems pretty easy.
From wikipedia on NP-complete:
In computational complexity theory, the complexity class NP-complete (abbreviated NP-C or NPC) is a class of decision problems. A decision problem L is NP-complete if it is in the set of NP problems so that any given solution to the decision problem can be verified in polynomial time, and also in the set of NP-hard problems so that any NP problem can be converted into L by a transformation of the inputs in polynomial time.
For NP-complete problems like the Boolean satisfiability problem (SAT) I see why the verification is made in polynomial time (you just test and get 0 or 1 ?) but in the partition problem, if their is no perfect partition (0 if total sum is pair or 1 if total sum is impair) I don't see how you can verify if your solution is the best in polynomial time ? I don't see how you can do it without testing all the other possibilities ? is it just because you can prove this problem to be equivalent to the SAT problem (1) or their is an explicit algorithm existing ?
Am I missing something ? If you can advice me good documentation about possible algorithm in polynomial time to verify a solution it would be perfect.
(1)In computational complexity theory, the Cook–Levin theorem, also known as Cook's theorem, states that the Boolean satisfiability problem is NP-complete. That is, any problem in NP can be reduced in polynomial time by a deterministic Turing machine to the problem of determining whether a Boolean formula is satisfiable.
EDIT: An example
let's say I have a set.
If I find a perfect partition: OK it's easy to check that it is the best.
Now suppose, I find a partition whose difference is 28 and let imagine there is only one better possible partition.
According to the NP completeness of the problem is there an explicit polynomial algorithm to do it. But I don't see how to prove that my solution is the best one without testing all other possibilities.