Cheap and Secure Web Hosting Provider : See Now

# [Answers] How to apply "verification" and "decision" for the SUBSET SUM problem?

, ,
Problem Detail:

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?

#### Answered By : Yuval Filmus

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.