CMI2014-A-04

Question

Alan’s task is to design an algorithm for a decision problem $P$. He knows that there is an algorithm $A$ that transforms instances of $P$ to instances of the Halting Problem such that $\text{yes}$ instances of $P$ map to $\text{yes}$ instances of the Halting Problem, and $no$ instances of $P$ map to $\text{no}$ instances of the Halting problem. Which of the following is true?

• A. The existence of $A$ implies the existence of an algorithm for $P$.
• B. The existence of $A$ implies that there is no algorithm for $P$.
• C. The existence of $A$ says nothing about whether there is an algorithm for $P$.
• D. The Halting Problem can be solved using $A$.

Answer 1