Appendix . Multiple Choice Questions (Set II)

In each of the following questions, choose the correct answer from the four choices provided.

1.

Consider three decision problems P1, P2 and P3. It is known that P1 is decidable and P2 is undecidable. Which one of the following is TRUE?

  1. P3 is decidable if P1 is reducible to P3

  2. P3 is undecidable if P3 is reducible to P2

  3. P3 is undecidable if P2 is reducible to P3

  4. P3 is decidable if P3 is reducible to P2’s complement

2.

Consider three problems P1, P2 and P3. It is known that P1 has polynomial time solution and P2 is NP-complete and P3 is in NP. Which one of the following is true.

  1. P3 has polynomial time solution if P1 is polynomial time reducible to P3

  2. P3 is NP complete if P3 is polynomial time reducible to P2

Get Introduction to Formal Languages, Automata Theory and Computation now with the O’Reilly learning platform.

O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.

Start your free trial