3
$\begingroup$

The SUBSET SUM problem states that:

Given finite set S of integers, is there a subset whose sum is exactly t?

Can someone show me why verification is simpler than decision for this problem?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

If anybody could show you that verification is simpler than decision, then she would be famous, having solved the P vs. NP problem.

For SUBSET-SUM, verification means that given a set $S$ which has a subset summing to $t$, someone can convince you easily that this is the case. The way she would do it is by giving you a subset of $S$ summing to $t$.

In contrast, decision means given a set $S$ and a target $t$, decide whether there is a subset of $S$ that sums to $t$. Nobody knows how to do it efficiently, and we conjecture that there is in fact no way to do it efficiently.

A related problem is co-verification: given a set $S$ which has no subset summing to $t$, we want someone to convince us easily that this is the case. Nobody has any idea how such a convincing argument would look like, and we conjecture that there such convincing arguments don't in fact exist (in general). This is the NP vs. coNP problem.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Hmm seems like there is a keyword that is missing and preventing this from clicking inside of my head. For decision, I'm imaging a set S and an integer t, if I were to "decide" if there exists a subset $S$ that sums to t, wouldn't this be the same as verification? Of course there is no one who could instantly tell if a subset exists without going through the computation (or at least to see what is in the set). Is that what you mean by no way to do it efficiently? Or do you mean that a set could be too complex (too many numbers) so it is difficult to check? $\endgroup$
    – Fraïssé
    Dec 3, 2014 at 4:22
  • $\begingroup$ What I mean by their being to way to do it efficiently is that there is no polynomial time algorithm that given $S$ and $t$ decides whether some subset of $S$ sums to $t$. It doesn't have to "go through the computation", if by that you mean checking all subsets. Hypothetically there could be more complicated algorithms which are polynomial time. The conjecture P$\neq$NP states that no matter how complicated it is, no algorithm solving SUBSET-SUM runs in polynomial time. $\endgroup$
    – Yuval Filmus
    Dec 3, 2014 at 4:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.