Find subset sum problem verifier and its complexity

Question

As homework we need to find a P-verifier for the subset sum problem.

Given: natural numbers $a_1, \cdots, a_n$ and $b$

Output: YES if there is a subset $S \subseteq \{a_1,\cdots,a_n\}$ where $\sum_{a \in S} = b$. NO otherwise.

My idea:

There is a verifier $V$ with a subset C as the certificate

$V=$ on input ((S,b),C)

1. Test whether the sum of the numbers in C equals b
2. Check if $C \subseteq S$
3. Output YES if 1 and 2 are true, output NO otherwise

As well as the time complexity if the input is unary encoded.

I am not quite sure about the time compexity.

1. $O(n)$ as it only has to sum up
2. not sure here
3. $O(n)$

Any hints would be great.

Answer 1

A trivial way to check $C \subset S$ is by searching over $S$ for each element in $C$. First, check if $C$ has at most $n$ elements, which can be done in $O(n)$ (otherwise, the answer is no). Then, for each element in $C$, compare it to all of the elements in $S$ to see if there is a match ($O(n)$ operations per element, and $O(n)$ elements, so this is $O(n^2)$). If there isn't a match for some element, you say no. If all elements have a match, then you say yes. So, this can be done in $O(n^2) + O(n) = O(n^2)$.

You don't need to have the best possible algorithm to show the existence of a P-verifier, just something which you can show that does it in polynomial time (which this does).