The GATE Grind

GATE 2014 CS (CS2) – Question 26

Theory of Computation · Turing Machines and Undecidability · 1 mark · Multiple choice

$A\le_mB$ means A is mapping (many-one) reducible to B. Which implication is FALSE?

  1. If $A\le_mB$ and B is recursive, A is recursive.
  2. If $A\le_mB$ and A is undecidable, B is undecidable.
  3. If $A\le_mB$ and B is recursively enumerable, A is recursively enumerable.
  4. If $A\le_mB$ and B is not recursively enumerable, A is not recursively enumerable.

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (D) If $A\le_mB$ and B is not recursively enumerable, A is not recursively enumerable.

Explanation

A computable reduction from A to B transfers a decider or recogniser for B back to A. However, a non-r.e. B can still have an easy language A reduce to it, for example a trivial language mapped to a fixed appropriate instance. Thus **D** is false; hardness cannot be inferred backwards in that direction.