closed by
1,059 views
0 votes
0 votes
closed as a duplicate of: GATE CSE 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 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.

 

closed by

Related questions

73 votes
73 votes
9 answers
1
Ishrat Jahan asked Oct 28, 2014
17,118 views
When $n = 2^{2k}$ for some $k \geqslant 0$, the recurrence relation$T(n) = √(2) T(n/2) + √n$, $T(1) = 1$evaluates to :$√(n) (\log n + 1)$$√(n) \log n$$√(n) \log...
0 votes
0 votes
0 answers
3
admin asked Jan 6
44 views
In software cost estimation, base estimation is related to :cost of similar projects already completed.cost of the base model of the present project.cost of the project w...