Introduction to Complexity ClassesWhat Is NPComplete? (Seminar)  
In Brief: The theory of algorithmic complexity is incomplete without the theory of complexity classes. Complexity classes like P, NP, NPC, coNP, 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. Target Audience:
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 coNP NPComplete NPHard, reductions of standard problems, Cook's theorem, NPCompleteness in the strong sense, known NPComplete 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. 
