edited by
13,212 views
19 votes
19 votes

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?

  1. $Q$ solves the subset-sum problem in polynomial time when the input is encoded in unary
  2. $Q$ solves the subset-sum problem in polynomial time when the input is encoded in binary
  3. The subset sum problem belongs to the class $\text{NP}$
  4. The subset sum problem is $\text{NP-hard}$
edited by

2 Answers

Best answer
28 votes
28 votes
Subset problem is NP-Complete - there is reduction proof but I don't remember (Can see the below link). So, (C) and (D) are true as an NPC problem is in NP as well as NPH.
 
Now, complexity of $Q$ is $O(nW)$, where $W$ is an integer.
  1. Input is encoded in unary. So, length of input is equal to the value of the input. So, complexity $= O(nW)$ where both $n$ and $W$ are linear multiples of the length of the inputs. So, the complexity is polynomial in terms of the input length. So, (A) is true.
  2. Input is encoded in binary. So, length of W will be $\lg W$. (for $W=1024$, input length will be just $10$). So, now $W$ is exponential in terms of the input length of $W$ and $O(nW)$ also becomes exponential in terms of the input lengths. So, $Q$ is not a polynomial time algorithm. So, (B) is false.

Correct Answer: $B$

edited by
2 votes
2 votes
The answer is B.  given that Algorithm Q solves this problem in O(nW) time. W is an integer (constant) so Q solves this problem in O(n) time.

Option A false because if the inputs are encoded in unary then Q solves this problem in O(1) time by just multiplying the unary number by N and checks whether it's equal to W or not.

Option B is True because we just need to iterate through the loop because the input is binary every time we have only two choices either add this to the sum or not when sum reaches to w answer is yes if no thought the loop then answer is no. it runs in O(n) time also

Options C and D false because given complexity of Algorithm Q is polynomial.
1 flag:
✌ Prohibited (Kumar Shresth “wrong answer and explanation”)
Answer:

Related questions

15 votes
15 votes
7 answers
3
Kathleen asked Sep 18, 2014
11,672 views
The problem $\text{3-SAT}$ and $\text{2-SAT}$ are both in $\text{P}$both $\text{NP}$ complete$\text{NP}$-complete and in $\text{P}$ respectivelyundecidable and $\text{NP}...
9 votes
9 votes
3 answers
4
Kathleen asked Sep 12, 2014
7,301 views
Which of the following problems is not $\text{NP}$-hard?Hamiltonian circuit problemThe $0/1$ Knapsack problemFinding bi-connected components of a graphThe graph coloring ...