Q. 8 The subset-sum problem is defined as follows: Given a set S of n positive integers
and a positive integer W; determine whether there is aa subset of S whose elements
sum to W.
An algorithm Q Solves this problem in O(nW) time. Which of the following
statements is false?
(A) Q sloves the subset-sum problem unpolynomial time when the input is
encoded in unary
(B) Q solves the subset-sum problem is polynominal time when the input is
encoded in binary
(C) The subset sum problem belongs to the class NP
(D) The subset sum problem in NP-hard
Answer: (b)
Explanation:
