Cheap and Secure Web Hosting Provider : See Now

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

, , No Comments
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?

Asked By : Beached Whale

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.

Best Answer from StackOverflow

Question Source :

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback