The subset-sum problem is defined as follows: Given a set S of n positive…
GATE · 2008 · CS
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.
Q solves the subset-sum problem in polynomial time when the input is encoded in binary
- C.
The subset sum problem belongs to the class NP
- D.
The subset sum problem is NP-hard
Attempted by 210 students.
Sign up free to check your answer
Sign up freeLoading lesson…