Out of the three decision problems P1, P2 and P3, P1 is decidable and P2 is undecidable. The statement that holds true is

Home / Engineering / Theory of Computation / Question

M

Mr. Dubey • 51.17K Points
Coach

Q.) Out of the three decision problems P1, P2 and P3, P1 is decidable and P2 is undecidable. The statement that holds true is

(A) P3 is decidable if P3 is reducible to compliment of P2

(B) P3 is decidable if P1 is reducible to P3

(C) P3 is undecidable if P1 is reducible to P3

(D) P3 is undecidable if P2 is reducible to P3

Correct answer : Option (D) - P3 is undecidable if P2 is reducible to P3

Share

Discusssion

Login to discuss.

Related MCQs on Theory of Computation

Q. Every poset that is a complete semilattice must always be a

Q. Which of the following makes sure that data is not changed when it not supposed to be?

Q. A feature F1 can take certain value: A, B, C, D, E, & F and represents grade of students from a college. Which of the following statement is true in following case?

Q. In human vision, the light into a sharp image is been focused by

Q. TOPIC 4.8 LEARNING TO RANK

Q. What will be the output of the following Python code? >>>print('new' 'line')

Q. Which block mode limits the maximum throughput of the algorithm to the reciprocal of the time for one execution?

Q. Trigger are not supported in

Q. The technique in which the CPU generates physical addresses directly is known as ____________

Q. ___________ is a function of the particular enterprise and application in an on-premises deployment.