The polynomial algorithm to show that the Partition Problem belongs to the class of NP

computational complexitycomputer sciencenp-complete

I just started to learn complexity. From my current understanding, the definition of NP is that:
A decision problem belongs to the class NP if every "Yes" instance has a certificate of its correctness that can be verified in polynomial time.

Now if we consider the Partition Problem with the input of a list of positive integers. The decision problem is whether you can split the set into two with the same sum.

Existing results tell us that the Partition Problem is NP-complete which means it belongs to the class of NP. Then my question is that what is the polynomial algorithm to verify the correctness of the "yes" instance?

For example, I have a "yes" instance $\{2,2,6,3,7\}$ for the partition problem. What is the polynomial algorithm to verify this?

Best Answer

The certificate could be a splitting of the list into two parts with the same sum. In this case, for example, $\{2,2,6\},\{3,7\}$. Your verification algorithm just has to check that this satisfies the requirements of the problem.