GATE-2008-44 closed

Question

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 NP
4. The subset sum problem is NP-hard

Please explain me how the option 1 is true.

 

Comments

Thank you

I checked it but I'm not able to understand how encoding in unary will make it polynomial.

If value of W become very high then no bits required will be high

What does W depends on?

---

If value of W become very high then no bits required will be high 
 

If W is very High we have to go for O(2ⁿ⁾

 

---

I checked it but I'm not able to understand how encoding in unary will make it polynomial.
 

Let's take the example What will the 10 in unary(Only 1 bit) Then we have write 10 times 1

1111111111

For 50 we have write 50 time like

1111111..........50 times. Ok

 So, the length of the 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.