Q15: Polynomial time reduction

Question #15: If we are able to reduce a problem P1 to another problem P2 in polynomial time, then which of the following statements are true?

(i) If P1 is decidable, then P2 is decidable.

(ii) If P2 is undecidable, then P1 is undecidable.

(iii) If P2 is decidable, then P1 is decidable.

(iv) If P1 is undecidable, then P2 is undecidable.

Options:

1. Both i and ii are true.

2. Both i and iii are true.

3. Both iii and iv are true.

4. All of them are true.

Solution:  If we could solve P2, then we could use its solution to solve P1 too. First, P1 can be reduced to P2 in polynomial time, then since P2 is decidable, P1 becomes decidable too. The counter positive statement is also true. Note that the reverse is not true. Even if P1 is decidable & could be reduced to P2 in polynomial time, nothing can be said about P2’s decidability, since the polynomial time reduction from P1 to P2 could complicate the problem. Therefore, 3rd option is the correct one.