Question

Consider the Coin Change problem:

Input: a set of positive integers coin denominations C = {C1, C2,..., Cn}, as well as a positive integer K.
Output: whether it is possible to make change K using coins of denominations in C, using at most one coin of each denomination.
Check ALL true statements:
a. Coin Change is in the class NP-hard.
b. There is solution for Coin Change that runs in time O(2").
c. Given a candidate solution to an instance of Coin Change, there exists an algorithm to verify if such solution is valid that runs in polynomial time.
d. One can solve the Coin Change problem using a dynamic programming approach in polynomial time.

Answer 1

a. Coin Change is in the class NP-hard.

c. Given a candidate solution to an instance of Coin Change, there exists an algorithm to verify if such a solution is valid that runs in polynomial time.

Step-by-step explanation:

The Coin Change problem is NP-hard, as it belongs to the class of problems for which a solution, once guessed, can be verified quickly. However, it doesn't necessarily mean it's in P, i.e., it may not have a polynomial-time algorithm for finding a solution. This is reflected in statement a.

For statement b, there is no known solution for Coin Change that runs in time O(2^n), where n is the size of the input. The problem is NP-complete, suggesting that finding a solution in exponential time is currently the best-known approach.

Statement c is true because given a set of coins and a proposed combination to make change for K, it's possible to verify in polynomial time whether the combination is valid by checking if the sum of selected coins equals K.

For statement d, there exists a dynamic programming approach to solve the Coin Change problem in polynomial time. By constructing a table and filling it incrementally, the algorithm achieves a polynomial runtime, making statement d true.