Decision Problems

 

Decision Problems

Both of the problems at the start were decision problems. Each instance gives an answer that is either true or false (yes or no). An instance that evaluates to yes is a yes instance and an instance that evaluates to no is a no instance.

Consider the following, simple examples. Are they yes or no instances of the subset sum problem?

●     The instance {2,3,6,8}, 8

The instance {1,3,4,7}, 13

The first instance {2,3,6,8}, 8 is a "yes" instance of the subset sum problem, because the subset {2,6} adds up to 8.

The second instance {1,3,4,7}, 13 is a "no" instance of the subset sum problem, because there is no subset of the set that adds up to 13.

Question

Is it easier to evaluate a yes instance of subset-sum than it is to evaluate a no instance? Think about both best and worst-case scenarios.

In general, it is easier to evaluate a "yes" instance of the subset sum problem than a "no" instance. This is because a "yes" instance can be determined by finding a single subset that adds up to the target sum, while a "no" instance requires checking all possible subsets and ensuring that none of them add up to the target sum.

In the best-case scenario, a "yes" instance can be determined in constant time by finding the subset that adds up to the target sum on the first pass through the input. A "no" instance can also be determined in constant time if the target sum is larger than the sum of all elements in the set.

In the worst-case scenario, a "yes" instance can be determined in O(2^n) time, where n is the number of elements in the set, by checking all possible subsets. A "no" instance can also be determined in O(2^n) time by checking all possible subsets and ensuring that none of them add up to the target sum.

Overall, it is generally easier to evaluate a "yes" instance of the subset sum problem than a "no" instance, due to the need to check all possible subsets for a "no" instance.