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 Answer 1

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$
1
  • $\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, 2019 at 22:55

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .