Unit 6

COMPUTATIONAL COMPLEXITY

1. Prove if L is a recursive language, so is L.
2. Explain post correspondence problem.
3. For a correspondence system ∑ = {0,1}, find solution sequence.
4. Explain non deterministic polynomial time.
5. If P1 is NP complete and there is a polynomial time reduction of P1 to P2, then P2 is NP complete.
6. Explain tractable and intractable problem in detail.
7. Explain node cover problem.
8. What is Clique problem? Explain NP complete problem,
9. Explain the following with example:

• Computational complexity
• 3 SAT problem

10. Difference between P class problem and NP class problem.