[Math] Partition Problem, verifying solution in polynomial time

algorithmsnp-complete

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.

Best Answer

NP completeness is defined for yes-no questions. An instance of the partition problem is a question of the form: given these sets does there exist a partition. This is proved to be NP complete. Questions of the form: given these sets and a positive integer k does there exist a partition into less than k sets are also decision problems (and are also NP complete by reduction to partition). Questions of the form: Given these sets what is the smallest (or largest) size of a partition is not a decision problem, and so cannot be NP complete or not NP complete. A question of that form can be NP-Hard

Related Question