Q128: Prove a new problem undecidable

Question #128: To prove a new problem undecidable, what would you do?

1. We convert any proven undecidable problem into this new problem.
2. We convert this problem to any proven undecidable problem.
3. We can prove any problem undecidable only by proving contradiction by first assuming that a hypothetical program exists.
4. Any one among option 1 and 2.

Solution:

If we reduce problem P1 to another problem P2, and if P1 is undecidable, then P2 is undecidable too. Because if P2 was decidable, then we could use its solution to solve P1 as well. Hence, the correct answer is option 1.

Q98: What problems classify as ‘decidable’ ?

Question #98: Which of the following is true?

Options:

1. The problems that can be solved by a computer are called decidable problems.
2. Intractability is the study of the problems which can be solved by a computer efficiently. NP hard problems are also known as intractable problems.
3. Intractable problems are decidable.
4. All of the above.

Solution: Since the problems which are hard to solve can still be solved given large amount of time, they are not undecidable. Correct option is the last one, all of the above.

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.