Course description
This course introduces the foundations of computational complexity theory and provides students with the tools to understand what makes computational problems easy or difficult to solve. We will study the main complexity classes and the relationships between them, with particular emphasis on P, NP, and NP-completeness. Students will learn how to classify computational problems and how to use polynomial-time reductions to establish their computational hardness.
The course will cover deterministic and nondeterministic computation, time and space complexity, polynomial-time reductions, and NP-complete problems. More advanced topics, including Turing reductions, the polynomial hierarchy, and randomized complexity classes, will also be introduced.
The course is intended for students interested in understanding the fundamental limits of computation and how these limits influence algorithm design in both theoretical and practical computer science.