About this course

\( \def\DTIME{\mathsf{TIME}} \def\NTIME{\mathsf{NTIME}} \def\DSPACE{\mathsf{DSPACE}} \def\NSPACE{\mathsf{NSPACE}} \def\P{\mathsf{P}} \def\NP{\mathsf{NP}} \def\L{\mathsf{L}} \def\NL{\mathsf{NL}} \def\PSPACE{\mathsf{PSPACE}} \def\NPSPACE{\mathsf{NPSPACE}} \def\EXP{\mathsf{EXP}} \def\NEXP{\mathsf{NEXP}} \def\RP{\mathsf{RP}} \def\coRP{\mathsf{coRP}} \def\ZPP{\mathsf{ZPP}} \def\PP{\mathsf{PP}} \def\FP{\mathsf{FP}} \def\sharpP{\#\mathsf{P}} \def\BPP{\mathsf{BPP}} \def\AC{\mathsf{AC}} \def\NC{\mathsf{NC}} \def\SC{\mathsf{SC}} \)

Complexity theory attempts to understand the amount of resources (time, space, energy, communication, randomness) that is necessary and sufficient to solve computational problems that can be solved by a model of computation (Classical or Quantum).

Starting in the early 60s, this study has resulted in many conceptual ideas about computation, randomness, and proofs being developed which subsequently ended up being deeply interrelated. In this course, we plan to cover some of these foundational ideas and connections.

To get a panoramic view of these connections, please check out this very well written book titled Mathematics and Computation by Avi Wigderson. For a broader perspective giving connection to mathematics and other fields, do have a look at Chapter 20 of this book.

Below is a tentative syllabus. We will not be able to cover all of it.

Tentative Syllabus

• Review of basic concepts: Turing machines, decidability and undecidability, diagonalization technique, non-determinisim
• Resource bounded computation: Notion of resource - formal definition and examples. Time and space as resource. Basic complexity classes $\DTIME$, $\NTIME$ and $\DSPACE$, $\NSPACE$. Configuration of a Turing machine. Basic containments. Time and space hierarchy theorem.
• Complexity classes: Classes - $\L$, $\NL$, $\P$, $\NP$, $\EXP$, $\NEXP$, $\PSPACE$, $\NPSPACE$. Problems - $UREACH$, $REACH$, $CVP$, $SAT$, $QBF$. Reduction between problems, complexity of reductions: logspace and polytime reduction, hardness and completeness. $SAT$ is $\NP$ complete (Cook-Levin), $REACH$ is $\NL$ complete.
• Space Complexity: Savitch’s theorem: $\NL \subseteq \L^2$, $\NL$ is closed under complementation.
• Oracle Turing Machines: Limits of Diagonalization - Baker-Gill-Solovay theorem. Polynomial hierarchy and quantifier characterisation.
• Boolean circuits and non-uniformity: Boolean circuits and $\P/poly$. Parallel complexity classes ($\AC$, $\NC$, $\SC$ and constant depth reductions if time permits)
• Randomness: Randomized complexity classes - $\RP$, $\coRP$, $\PP$, $\ZPP$, $\BPP$. Theorems: Karp-Lipton, Sisper-Gacs, Adleman
• Counting Complexity: Counting TMs, Class $\FP$, $\sharpP$, counting Perfect matchings, Permanent is $\sharpP$-complete.