Find subset sum problem verifier and its complexity 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.

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).