0
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Perfect. I was thinking of $n^2$ but was not sure. So also my verifier $V$ is correct then? $\endgroup$ – Chris May 26 '14 at 13:11
  • $\begingroup$ 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. $\endgroup$ – Batman May 26 '14 at 13:17

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.