...
Question 11772 – Sorting
February 20, 2024
Question 4473 – Research Aptitude
February 21, 2024
Question 11772 – Sorting
February 20, 2024
Question 4473 – Research Aptitude
February 21, 2024

Question 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 .
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.
0 0 votes
Article Rating
Subscribe
Notify of
0 Comments
Inline Feedbacks
View all comments
0
Would love your thoughts, please comment.x
()
x
error: Alert: Content selection is disabled!!