HiveBrain v1.2.0
Get Started
← Back to all entries
snippetMinor

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

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
sumproblemtheapplydecisionforhowandsubsetverification

Problem

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?

Solution

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.

Context

StackExchange Computer Science Q#33753, answer score: 3

Revisions (0)

No revisions yet.