Appendix . Multiple Choice Questions (Set II)
In each of the following questions, choose the correct answer from the four choices provided.
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?
P3 is decidable if P1 is reducible to P3
P3 is undecidable if P3 is reducible to P2
P3 is undecidable if P2 is reducible to P3
P3 is decidable if P3 is reducible to P2’s complement
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.
P3 has polynomial time solution if P1 is polynomial time reducible to P3
P3 is NP complete if P3 is polynomial time reducible to P2
Get Introduction to Formal Languages, Automata Theory and Computation now with O’Reilly online learning.
O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.