Question

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 a 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 solves the subset-sum problem in Polynomial time when the input is encoded in unary
• B. The subset sum problem belongs to the class NP
• C. Q solves the subset-sum problem is Polynominal time when the input is encoded in binary
• D. The subset sum problem is NP-hard

Answer 1

The correct option is C Q solves the subset-sum problem is Polynominal time when the input is encoded in binary

If an algorithm Q solves subset-sum problem in O(nW) time where w is an integer which is constant. So Q solves the subset-sum problem in O(n) time because W is a constant and input must encoded in binary.