Is p & np in syllabus ?

The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+9 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?

- $Q$ 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
- The subset sum problem belongs to the class NP
- The subset sum problem is NP-hard

+17 votes

Best answer

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.

- 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. - 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.

+1

Please explain this ENCODING thing.I am not able to understand how encoding in unary and binary come out to be proportional and exponential to input length respectively..

please explain. If possible, any example will be appreciated .

Thank You

please explain. If possible, any example will be appreciated .

Thank You

0

@Arjun In part b you said input is encoded in binary so logW. But what about values of n. Won't they be also encoded in binary. And then we can say that Q solves the problem in exponential time with both n and W as exponential inputs.

+1

when input in binary, say 1023, i.e. 10 1's, the time taken will be $(n\times(2^{10})-1)$, which is exponential.

- All categories
- General Aptitude 1.4k
- Engineering Mathematics 5.7k
- Digital Logic 2.2k
- Programming & DS 4.1k
- Algorithms 3.6k
- Theory of Computation 4.5k
- Compiler Design 1.7k
- Databases 3.2k
- CO & Architecture 2.8k
- Computer Networks 3.2k
- Non GATE 1.1k
- Others 1.5k
- Admissions 503
- Exam Queries 474
- Tier 1 Placement Questions 21
- Job Queries 61
- Projects 13

39,645 questions

46,729 answers

140,391 comments

58,088 users