Difficulty: Intermediate | Prerequisites: P, NP, and NP-hardness definitions; understanding of efficient verifiers; basic set/multiset notation.
Proving a language is in NP requires constructing an efficient verifier, and getting a verifier right is trickier than it looks. This topic walks through three attempts at verifying SubsetSum, each failing for a different reason: unsoundness, lack of polynomial certificate size, and a misunderstanding of the completeness requirement. These are exactly the kinds of mistakes that appear on exams, so understanding where each verifier breaks is as valuable as understanding how to build a correct one.
An efficient verifier must be sound (rejects when x is not in L for every certificate), complete (accepts when x is in L for at least one certificate), and efficient (runs in polynomial time with a polynomial-size certificate). Three verifiers for SubsetSum each violate one of these properties, and understanding why is the point of the exercise.
Soundness (of a verifier)
If x is not in L, then V(x, c) rejects for every certificate c. No false positives. In simple terms, the verifier never says "yes" when the answer is actually "no."
Completeness (of a verifier)
If x is in L, then there exists some certificate c such that V(x, c) accepts. At least one certificate works. In simple terms, for a genuine "yes" instance, there is always a way to prove it.
Efficiency (of a verifier)
The certificate c has polynomial size in |x|, and V runs in polynomial time in |x|. Think of it as: checking the proof is fast, and the proof itself is not unreasonably long.
SubsetSum
The language {(S, k) : S is a multiset of non-negative integers, and some submultiset of S sums to k}.
Multiset
A collection that allows duplicate elements. A submultiset may not contain more copies of any element than the parent multiset does.
Certificate (in context)
For SubsetSum, a natural certificate is a bit array C[1..n] indicating which elements of S to include. This has size exactly n, which is polynomial.
Takes a multiset C as certificate and checks: is each element of C in S, does |C| <= |S|, and does sum(C) = k?
The flaw: C need not be a submultiset of S. It only checks that each element of C appears somewhere in S, but C can reuse elements more times than S contains them.
Counterexample: S = {2, 3, 5}, k = 4, C = {2, 2}. Each element of C (the value 2) is in S, and 2 + 2 = 4, so the verifier accepts. But {2, 2} is not a submultiset of S (S contains only one copy of 2), so (S, 4) is not actually in SubsetSum.
Secondary issue: C is not guaranteed to be polynomial in size with respect to (S, k), so reading C alone could be inefficient.
Fix: restrict C to be a submultiset of S (check multiplicity, not just membership).
Takes a collection of multisets {C1, C2, ..., Cm} as certificate. For each Ci, confirms Ci is a submultiset of S and checks if sum(Ci) = k.
The verifier is correct (both sound and complete). Any submultiset that sums to k will be found if it is in the collection.
The flaw: the proof never establishes that C has polynomial size. If C is the entire power set of S, then m = 2^n and the verifier runs in time O(2^n * n), which is exponential in the instance size.
The verifier runs in polynomial time with respect to its total input (S, k, C), but not with respect to the instance (S, k) alone. This distinction matters.
Takes a bit array C[1..n] as certificate. For each i, if C[i] = 1, add s_i to the running sum. Accept if sum = k.
Certificate size: exactly n bits, which is polynomial in the instance size.
Upsilon's counterexample: S = {1, 1, 2, 5}, k = 7, C = [0, 1, 0, 1]. This gives 1 + 5 = 6, not 7, so the verifier rejects.
Why Upsilon is wrong: completeness says "there exists some c" that makes V accept, not that every c makes V accept. For this instance, C = [1, 1, 0, 1] gives 1 + 1 + 5 = 7, and C = [0, 0, 1, 1] gives 2 + 5 = 7. Both are valid certificates.
A verifier rejecting one bad certificate does not make it incorrect. It only needs to accept for at least one valid certificate per "yes" instance.
Students often think a verifier must accept every valid certificate for a "yes" instance. It need not. Completeness requires only that at least one certificate leads to acceptance.
A verifier that is sound and complete can still fail to show a language is in NP if the certificate is not polynomial in size. Correctness and efficiency are separate requirements.
Checking that an element is "in" a multiset is not the same as checking submultiset membership. Multiplicity matters: {2, 2} is not a submultiset of {2, 3, 5}.
Students sometimes conflate "polynomial in the total input size" with "polynomial in the instance size." A verifier must run in poly time with respect to the instance (S, k), not just (S, k, C).
Expect questions that present a broken verifier and ask you to identify the flaw. The three failure modes (unsound, inefficient certificate, misunderstanding completeness) cover the main exam patterns.
When writing your own verifier, always address: (1) what is the certificate, (2) is it polynomial size, (3) soundness, (4) completeness, (5) polynomial runtime.
The bit-array certificate (VerifierC) is the standard approach for SubsetSum. Know it cold.
True or False: A verifier that accepts S = {2, 3, 5}, k = 4, C = {2, 2} is sound. (False, this is not a valid submultiset.)
Fill in the blank: VerifierB's flaw is that the certificate C is not guaranteed to be ______ in size. (polynomial)
True or False: If a verifier rejects some certificate for a "yes" instance, the verifier is incorrect. (False, completeness only requires one accepting certificate.)
True or False: A correct but inefficient verifier proves a language is in NP. (False, efficiency is required.)
Q: VerifierA accepts S = {2, 3, 5}, k = 4, C = {2, 2}. Is (S, 4) in SubsetSum? What property does this violate?
A: No, (S, 4) is not in SubsetSum because no submultiset of {2, 3, 5} sums to 4. The verifier falsely accepts, violating soundness.
Q: VerifierB is both sound and complete. Why does it not prove SubsetSum is in NP?
A: The proof never shows the certificate has polynomial size. The collection C could contain exponentially many multisets (up to 2^n), so the verifier does not run in polynomial time with respect to the instance size (S, k).
Q: Upsilon claims VerifierC is incorrect because it rejects S = {1, 1, 2, 5}, k = 7, C = [0, 1, 0, 1]. Why is this claim wrong?
A: Completeness requires that there exists some c for which V accepts, not that every c leads to acceptance. The certificates C = [1, 1, 0, 1] and C = [0, 0, 1, 1] both cause VerifierC to accept this instance.
This connects directly to the P, NP, NP-Hardness topic, since constructing a verifier is how you prove membership in NP (the first half of any NP-completeness proof). It also connects to the Dominating Set and Subgraph Isomorphism problems, where you will need to build verifiers from scratch.
SubsetSum, efficient verifier, soundness, completeness, certificate size, polynomial-size witness, multiset, submultiset, bit array certificate, NP membership proof, EECS 376, verifier construction, false positive, power set, brute-force certificate enumeration