Introduction to Complexity Classes
What Is NP-Complete? (Seminar)
In Brief: The theory of algorithmic complexity is incomplete without the theory of complexity classes. Complexity classes like P, NP, NP-C, co-NP, etc. are of utmost theoretical importance. In practice, they help us understand more about the hardness of the problem we are trying to tackle. This introductory seminar will give the student a firm grasp on the theoretical underpinnings of the theory of complexity classes.
Teacher's Introduction: Abhishek Rathod did his B.E. in CS from VIT. He was a research trainee at the Computational Mathematics Laboratory (CML) at TIFR from July 2003 to June 2004. He unofficially continues to work at the same place, but is currently also pursuing his own theoreitcal interests. His research interests are complexity theory, optimization theory and combinatorics.
Course Topics: Basic ideas, motivations, theory of P NP co-NP NP-Complete NP-Hard, reductions of standard problems, Cook's theorem, NP-Completeness in the strong sense, known NP-Complete problems from different fields.
Prerequisites: Basic understanding of TCS and algorithms would be useful. (DAA should be enough.)
Advanced Courses: This course is a prerequisite for Abhishek's course on satisfiability problems.