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.

• Computer Science students
• People who took DAA and have the heart for more theoretical work
• People who wish to further study Satisfiability Theory
• People from industry/academia who design algorithms
• As usual, anybody who is interested – the more the merrier

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.