Computational Complexity Basics
Time and space complexity classes.
Hierarchies and relationships.
Polynomial Time and Tractability
Class P (Polynomial time).
Significance in algorithm design.
Introduction to NP-Completeness
Class NP (Nondeterministic Polynomial time).
Verification vs. computation.
Reductions and Problem Transformations
Concept of polynomial-time reductions.
Cook-Levin theorem (overview).
NP-Complete Problems
SAT Problem.
Traveling Salesman Problem.
Clique problem.
Approaches to NP-Complete Problems
Approximation algorithms.
Heuristic methods.
Intractable and Undecidable Problems
Provably intractable problems.
Halting problem and undecidability.
Complexity Classes Beyond NP
Brief overview of classes like PSPACE, EXPTIME.