Q44

MCQ2 marks, −0.5

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 $\text{NP}$

(D)

The subset sum problem is $\text{NP-hard}$

Loading…