Project ForgeThe 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?
- AQ 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
- CThe subset sum problem belongs to the class NP
- DThe subset sum problem is NP-hard
Explanation
O(nW) is pseudo-polynomial: with UNARY encoding, W's representation size IS W, so O(nW) is genuinely polynomial in input size (TRUE). With BINARY encoding, W's size is log W, so O(nW) = O(n·2^(log W)) is EXPONENTIAL in input size — NOT polynomial, making (B) the false statement. (C) and (D) are standard true facts about subset-sum.
Source: GATE CS 2008 (2008)
This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.