Complexity Theory: CSL7140
"I conjecture that there is no good algorithm for the traveling salesman problem. My reasons are the same as for any mathematical conjecture: (1) It is a legitimate mathematical possibility, and (2) I do not know."
– Jack Edmonds, 1966
Course Description
Complexity Theory is a subset of Theoretical Computer Science that primarily focuses on proving the nonexistence of efficient algorithms for computational problems, classifying problems based on the amount of resources required to solve them, and comparing different classes of problems.
A few questions that we will explore in this course are:- Can you solve every problem if you have unbounded time and space?
- Are there problems solvable in exponential time that are not solvable in polynomial time?
- Can randomization give us simpler and more efficient algorithms for some problems?
- Are there hard problems whose solutions are also hard to verify?
- Is it possible to make small and efficient silicon chips to solve the famous 3SAT problem when the formula has at most 1000000 variables?
Course Information
Prerequisites
CSL2020 and CSL2040 or working knowledge of Algorithms and Discrete Mathematics.
Books
- Computational Complexity: A Modern Approach by Sanjeev Arora and Boaz Barak.
Evaluations
- 20% - Quizzes (MCQs, T/Fs) (best 2 out of 3 quizzes)
- 30% - Minor
- 50% - Major
- 0% - Practice problems whose variants may come in exam
-  Bonus 1% - For every first catch of an error during the lectures
Office Hours
Mail me to fix an appointment