Computational complexity. Time-space complexities. Speedup, hierarchy theorems. Time-Space Tradeoff. Translational Lemmas. Gap and Union theorems. Intractable problems – polynomial time space. Theory of NP-Completeness – Classes, P, NP, Co-NP, PSPACE. Poly-Time and Log-Space transformations. Proof techniques for establishing NP-Completeness. Turing Reducibilities and polynomial hierarchy. Using NP-Completeness to Analyze problems. NP-Hardness. Introduction to Approximation algorithms to hard problems.​