CSE526A: P vs NP

About the course

Description: For many years, and to a significant number of computer science researchers, the "P-NP" problem was THE central problem in Computer Science. The problem asks if the complexity class P is equivalent to that of NP, or not. Even though today a number of other significant problems have been identified, nevertheless, this problem still keeps everyone guessing and has even gained popularity outside the community. The focus of this course will be to understand the significance of this problem. Part of the course will focus on the approaches to solve it or bypass it, and another part will discuss its wide ranged implications. The techniques will be based on Computational Complexity theory, and the necessary tools will be introduced during the course itself. After taking this course, you will

  • Understand the notion of complexity classes and reductions
  • Understand the notion of oracles and hierarchies and relativization
  • Know about the complexity classes P, NP and related classes
  • Understand the formal implications of the question P!=NP

These topics are planned for this course: Machine models, Turing Machine, Notion of Language, Notion of Problem,   Reductions,  Basic complexity classes: P, NP, PH, EXP,  NP completeness proofs, Relativization, Coping with NP hardness