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?
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.Sign up to join this community
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.