The GATE Grind

GATE 2015 CS (CS3) – Question 41

Algorithms · Asymptotic Analysis and Time/Space Complexity · 2 marks · Multiple choice

L1≤pL2, L3≤pL2 and L2≤pL4. Which are guaranteed?
I: L4∈P implies L2∈P.
II: L1∈P or L3∈P implies L2∈P.
III: L1∈P iff L3∈P.
IV: L4∈P implies L1,L3∈P.

  1. II only
  2. III only
  3. I and IV only
  4. I only

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (C) I and IV only

Explanation

A polynomial algorithm for the target of a polynomial reduction gives one for its source. Thus L4 in P yields L2 in P and, by composing reductions, both L1 and L3 in P. Easiness does not generally transfer from a source to its target, and sharing a target does not equate source complexity. Hence I and IV, C.

More Asymptotic Analysis and Time/Space Complexity questions

All Asymptotic Analysis and Time/Space Complexity questions →