2
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ OK, so that is what the "certificate" means. I guess I had some misunderstanding on the definitions of Class NP. $\endgroup$ – Mathexx Jul 31 at 22:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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