Computational Complexity Theory

Welcome to computational complexity theory.

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
5. Quiz B

Lectures

1. Boolean circuits and Karp-Lipton theorem (Apr 10)

   We defined Boolean circuit families. We saw that all functions, even undecidable ones, can be computed by Boolean circuit families. We proved Karp-Lipton theorem, which shows that SAT is unlikely to have small Boolean circuits.

2. Public coin protocol for GNI (Mar 27)

   We finished the proof of set counting protocol and saw how to apply it to GNI.

3. Public coin protocol for GNI (Mar 24)

   We started the proof of Goldwasser-Sipser protocol for turning any private coin protocol into an equivalent public coin protocol. We defined pairwise independent hash families.

4. IP is in PSPACE (Mar 20)

   We proved that IP is in PSPACE by simulating an optimal prover. We proved that coNP is in IP.

5. IP is in PSPACE using public coins (Mar 17)

   We tried to prove IP is in PSPACE. However, the proof assumed verifier's randomness is public. This is true but not required.

6. Interactive Proofs (Mar 13)

   We defined the class of Interactive Proofs (IP). We saw that with a deterministic verifier, this is the same as NP. We saw that with randomness, IP contains Graph Non-Isomorphism, a language seemingly not in NP.

7. NL = coNL (Mar 10)

   We saw that non-reachability in directed graphs can be proved using a logspace verifiable and read-once proof. The proof used a technique called inductive counting. The prover inductively convinces the verifier of the number of vertices reachable from the source in at most i steps for i from 1 (trivial) to n. Once the number of vertices reachable from the source is known, the prover gives the verifier a list of proofs of reachability of those vertices in increasing order of those vertices.

8. 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.

9. 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.

10. 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.

11. 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.

12. 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.

13. 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.

14. 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.

15. 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.

16. 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.

17. 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.

18. 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)?