Complexity Theory

CSE421/CSE621
4

Computational problems can be studied from the point of view of computational resources (e.g., running time) required to solve them - this forms the notional of computational difficulty. Apart from the nature of the problem, the difficulty also depends on the underlying model of computation, including non-deterministic, non-uniform and randomized models. Problems can be related to each other based on their resource usage, and problems with similar difficulty can be grouped together to form a classification of computational problems into complexity classes. Computational complexity is about studying the above concepts, and is especially concerned with giving precise upper and lower bound on the amount of resources required to solve certain problems. This has had a profound impact on current algorithm design and cryptography, and still sees applications in areas outside of theoretical computer science.

  1. Knowledge of different models of computation and their relationships
  2. Ability to bound resource usage (e.g., time, space, circuit size, depth) required for problems under different models of computation
  3. Ability to place a problem in the hierarchy of computational complexity classes
  4. Ability to show separations, collapses of classes and prove completeness of problems
  5. Understand the major questions (e.g., P =? NP) and their role in other fields of computer science
  6. Develop knowledge of randomized complexity classes and ability to perform randomized reductions
    Monsoon

    Course Offering