Computational Complexity Theory

Welcome to computational complexity theory. Please read the learning outcomes for the course.

Evaluation

There will be four written exams — A, B, Midsem (M), and Endsem (E). Each will contribute 25%. The performances in exams will only be considered up to a cut-off grade.

For higher grades than the written exam cut-off grade, a student has to do take-home written assignments that will test advanced problem solving skills. These will only be considered if the performance in written exams is good. If I feel that further evaluation is necessary, then I may conduct a viva too. Final grade may be revised upward or downward depending on the performance in viva.

Questions

1. Quiz A
2. Take-home 1
3. Worksheet 1
4. Mid-sem

Lectures

1. Nondeterministic LOGSPACE (Feb 17)

   We explored how to define a logspace verifier and saw that just limiting read-write tape to logspace yields NP. We saw nondeterministic logspace algorithm for directed graph REACHability (REACH). We saw that REACH has a log²-space algorithm.

2. LOGSPACE (Feb 10)

   We defined the class LOGSPACE. We defined log-space, many-one reductions using write-only tapes. We showed log-space reductions compose and the class LOGSPACE is closed under log-space reductions. We showed that the reachability problem in undirected forests is in LOGSPACE.

3. QBF is PSPACE-hard (Feb 03)

   We proved that QBF is PSPACE-hard by defining configuration graphs for TM on input x. We then built a small quantified Boolean formula that is equivalent to reachability in configuration graphs.

4. PH, Space, PSPACE (Jan 30)

   We defined the complexity class Polynomial Hierarchy (PH), the class of problems characterized by Boolean formulas with a fixed number of alternating quantifiers. We then defined space complexity, defined the problem Quantified Boolean Formulas (QBF), and showed that QBF is in PSPACE using a recursive algorithm.

5. Detailed proof of Cook-Levin theorem (Jan 27)

   We saw the details of the proof of a simpler theorem, Circuit SATisfiability (CSAT) is NP-complete. We can reduce CSAT to Formula SATisfiability (FSAT) to prove Cook-Levin theorem. We also saw that problems like EXACT-VERTEX-COVER is likely neither in NP nor in coNP as it needs both existential and universal quantifiers when reducing to FSAT.

6. Outline of the proof of Cook-Levin theorem (Jan 23)

   We defined non-deterministic TMs and their time. We proved that NP is also the class of languages with poly-time non-deterministic TMs. We then saw an outline of the proof that SAT is NP-complete.

7. Reductions (Jan 20)

   We defined poly-time Turing reductions and poly-time many-one reductions. We proved that poly-time Turing reductions compose and the class P is closed under them. We saw that the class NP is may be not closed under poly-time Turing reductions but it is closed under poly-time many-one reductions.

8. P, NP, coNP (Jan 16)

   We saw why poly-time is considered a robust time complexity function. We defined the classes P, NP, and coNP and proved basic relationships between them. We defined NP and coNP as classes of languages with poly-time verifier and poly-time refuter respectively.

9. Time complexity (Jan 13)

   We defined the time complexity of a language. We saw that time complexity is susceptible to small changes in the machine model and argued that poly-time does not suffer from this problem. We proved the time hierarchy theorem using diagonalization.

10. Turing machines (Jan 09)

    We defined Turing machines (TM) with special focus on the word constant. Constant means independent of the size of the input.

11. Overview of the course (Jan 06)

    We saw an overview of the major questions in computational complexity theory. Is verification easier than solving (P vs NP)? Can all fast sequential algorithms be parallelized (P vs NC)? Can we build good circuits for hard problems (NP vs P/poly)? Does interactivity help in proofs (NP vs IP)?