GATE CS 2005 Q45 — Undecidability

To determine the correct statement, we use the fundamental properties of mapping reducibility. Let $A \le B$ denote that problem $A$ is reducible to problem $B$. This reduction implies that $B$ is at least as hard as $A$.

From this definition, we have two key rules:

1. If $B$ is decidable, then $A$ is also decidable.
2. If $A$ is undecidable, then $B$ is also undecidable.

We are given:

• $P_1$ is decidable.
• $P_2$ is undecidable.

Let us analyze the options based on these rules:

• Option A: $P_1 \le P_3$. Since $P_1$ is decidable, reducing it to $P_3$ gives no information about the decidability of $P_3$ ($P_3$ could be either decidable or undecidable). Thus, this statement is false.
• Option B: $P_3 \le P_2$. Since $P_2$ is undecidable, reducing $P_3$ to $P_2$ does not force $P_3$ to be undecidable ($P_3$ could be decidable). Thus, this statement is false.
• Option C: $P_2 \le P_3$. Since $P_2$ is undecidable, any problem $P_3$ that is at least as hard as $P_2$ must also be undecidable. Thus, $P_3$ is undecidable. This statement is true.
• Option D: $P_3 \le \overline{P_2}$. Since $P_2$ is undecidable, its complement $\overline{P_2}$ is also undecidable. Reducing $P_3$ to an undecidable problem does not guarantee that $P_3$ is decidable. Thus, this statement is false.