The GATE Grind

GATE 2008 CS – Question 44

Theory of Computation · Turing Machines and Undecidability · 2 marks · Multiple choice

Subset sum: given n positive integers S and positive W, determine whether a subset sums to W. Algorithm Q takes O(nW) time. Which is false?

  1. Q is polynomial when input is unary.
  2. Q is polynomial when input is binary.
  3. Subset sum belongs to NP.
  4. Subset sum is NP-hard.

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (B) Q is polynomial when input is binary.

Explanation

We are sorry we couldn't write detailed soluition for this, we are working on it!, please consider asking your own AI, its just 2-3 clicks with very minimum effort

More Turing Machines and Undecidability questions

All Turing Machines and Undecidability questions →