Question 11772 – Sorting
February 20, 2024Question 4473 – Research Aptitude
February 21, 2024Question 6293 – CHENNAI MATHEMATICAL INSTITUTE – M.Sc. / Ph.D. Programme in Computer Science ( 15 May 2014 )
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 yes instances of P map to yes instances of the Halting Problem, and no instances of P map to no instances of the Halting problem. Which of the following is true.
Correct Answer: C
Question 4 Explanation:
The reduction is from P to the Halting Problem, so we cannot infer undecidability of P .
The existence of A implies the existence of an algorithm for P .
The existence of A implies that there is no algorithm for P .
The existence of A says nothing about whether there is an algorithm for P .
The Halting Problem can be solved using A.
Subscribe
Login
0 Comments