Theory of Computational Complexity

This course introduces students to the basics of computational complexity theory. They will study various concepts in models of computation, time and space complexity, hierarchy of complexity classes, diagonalization techniques, NP-completeness, and oracle/relativized computation. In addition to the theoretical concepts, the theory classes will cover some standard theoretical notions and definitions, proof techniques, and techniques for separating various complexity classes. The tutorials will take several exercises and examples and cover the topics in greater depth.

Computational complexity theory provides computer scientists with concepts, models, and formalisms for reasoning about the resources (such as time or memory space) needed to carry out computations and the efficiency of the computations that use these resources. It provides tools to measure the difficulty of combinatorial problems, both absolutely and in comparison with other issues. Courses in this subject help students gain analytic skills and enable them to recognize the possible limits of computation. Here, the students learn the fundamental models of computation, the limitations of computation, and the distinctions between feasible and intractable. In particular, NP-completeness and NP-hardness have pervaded much of science and transformed computer science, with which the students will be familiarized in this course.

This course can be taken together with "Theory of Computation."

By the end of this course, each student will have had the opportunity to:

• Read and write formal proofs in complexity theory.
• Understand various separating and identifying techniques and when they can be applied.
• Know different complexity classes and comprehend what they can be applied to.

After completing this course, students should be able to

1. Learn the basic vocabulary of Complexity Theory | Know/Knowledge Outcome
2. Understand reduction techniques and complexity classes| Comprehend Outcome
3. Prove theorems and compare algorithms with each other| Apply Outcome
4. Know the possible optimal algorithms in complexity sense | Analysis Outcome
5. Critique the efficacy and efficiency of various algorithms | Evaluate Outcome
6. Design more efficient algorithms for different problems | Create/synthesize Outcome

Main Text (1, Chapters 3-7):

1. Computability and Complexity Theory, authored by Alan L Selman & Steven Homer, published in 2011 (2nd Edition (Springer). 
   https://link.springer.com/book/10.1007/978-1-4614-0682-2
2. Computability and Complexity: Foundations and Tools for Pursuing Scientific Applications, authored by Rod Downey, Published in 2024 (Springer).
   https://link.springer.com/book/10.1007/978-3-031-53744-8

• Dexter C. Kozen, “Theory of Computation,” Springer (2006)
• Martin Davis & Ron Sigal & Elaine J. Weyuker, “Computability, Complexity, and Languages: Fundamentals of Theoretical Computer Science,” Morgan Kaufmann (1994, 2nd ed.)