2
$\begingroup$

The original SUBSET-SUM problem is "given a set of integers, is there a non-empty subset whose sum is zero?"

If we look at the inverse problem: "given a finite set of integers, does every non-empty subset have a nonzero sum?"

I understand how the verifier and certificate are used to determine SUBSET-SUM to be in NP.

I know it is unknown is NP = coNP.

But am I right when I say that the inverse problem has a verifier and certificate? The certificate being "every non-empty subset" and the verifier verifies every single subset. This will not be a polynomial verifier so it won't be in NP, but am I correct to assume that this is indeed a verifier and certificate?

$\endgroup$
1
$\begingroup$

For such a set to be a certificate for the complement of SUBSET SUM the verifier not only has to verify that each subset in the certificate sums to a non-zero value. The verifier also has to verify that every subset in the certificate is derivable from the original set and verify that no additional subsets beyond those in the certificate can be derived. If your verifier does all that, then you have a verifier and a certificate. But since this is equivalent to brute-force solving the problem twice (once to generate the certificate, once to verify the certificate), it's kind of pointless. Brute-forcing the problem once is infeasible enough.

$\endgroup$

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.