Complexity Theory and Applications

Description

This is a first course in complexity theory, with emphasis on the hardness and intractability of problems. Tools for identifying NP-complete problems as well as polynomial reductions between problems are given. Different strategies for dealing with NP hard problems are presented, this includes approximation techniques as well as randomization methods. Other complexity classes such as NC, BPP, RP will be defined and explained.

Program

Master in Computer Science

Objectives

• The students will be able to:
  • Understand the principles of complexity theory and learn a few of the complexity classes.
  • Identify NP-complete problems in a variety of diverse fields and applications.
  • Find methods to deal with the hard problems and produce efficient solutions.