0

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.

Chris
  • 521

1 Answers1

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

Batman
  • 19,390
  • Perfect. I was thinking of $n^2$ but was not sure. So also my verifier $V$ is correct then? – Chris May 26 '14 at 13:11
  • Yep, though I'd test if $|C| \leq n$ while summing them, and remove it from step 2. Step 3 is $O(1)$ trivially, since you're just checking if step 1 and step 2 returned true. – Batman May 26 '14 at 13:17