UPPCL AE 2022
October 23, 2023Arrays
October 23, 2023GATE 2008
|
Question 44
|
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
An algorithm Q solves this problem in O(nW) time. Which of the following statements is false?
|
Q solves the subset-sum problem in polynomial time when the input is encoded in unary
|
|
|
Q solves the subset-sum problem in polynomial time when the input is encoded in binary
|
|
|
The subset sum problem belongs to the class NP
|
|
|
The subset sum problem is NP-hard
|
Question 44 Explanation:
Note: Out of syllabus.
Correct Answer: B
Question 44 Explanation:
Note: Out of syllabus.