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.43K 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. Which of the following HTTP methods should be idempotent in nature?

Q. Perforated paper used as input of output media is known as

Q. From the options below, which of them is not a vulnerability to information security?

Q. What will happen when a process terminates?

Q. How many digits of the DNIC (Data Network Identification Code) identify the country?

Q. Com in Latin is

Q. In transport layer, Multiplexing is done at

Q. One reason for using the sum-of-products form is that it can be implemented using all gates without much difficulty.

Q. What is the difference between struct and class in C++?

Q. In order to assess how much information is brought by each component, and the correlation among them, a useful tool is the .