Q45

MCQ2 marks, −0.5

Consider three decision problems $P_1$ , $P_2$ and $P_3$ . It is known that $P_1$ is decidable and $P_2$ is undecidable. Which one of the following is TRUE?

(A)

$P_3$ is decidable if $P_1$ is reducible to $P_3$

(B)

$P_3$ is undecidable if $P_3$ is reducible to $P_2$

(C)

$P_3$ is undecidable if $P_2$ is reducible to $P_3$

(D)

$P_3$ is decidable if $P_3$ is reducible to $P_2$ 's complement

Loading…