NOC:Basics of Computational Complexity

Lecture 1 - Introduction

Lecture 2 - Outline

Lecture 3 - Formalize Problems and Machines

Lecture 4 - Turing Machine

Lecture 5 - Asymptotics, Church-Turing Thesis and UTM

Lecture 6 - Halting Problem and Diagonalization

Lecture 7 - Classes P, NP, EXP

Lecture 8 - Comparison of Classes and Non-determination

Lecture 9 - NP Vs Ntime

Lecture 10 - SAT is NP-hard

Lecture 11 - Cook-Levin Theorem

Lecture 12 - NP-Hardness and Co-Classes

Lecture 13 - NEXP and Godel's Computation Question

Lecture 14 - Time, Space Hierarchy

Lecture 15 - NDTM Hierarchy

Lecture 16 - Ladner's Theorem and Introduction to Oracles

Lecture 17 - Oracle and Relativizing Proofs

Lecture 18 - Non Relativizing P=NP and Introduction to Space Complexity

Lecture 19 - PSpace Completeness

Lecture 20 - QBF Game and NSpace

Lecture 21 - NL Complete

Lecture 22 - NL = coNL

Lecture 23 - Polynomial Hierarchy

Lecture 24 - Polynomial Hierarchy

Lecture 25 - PH Complete and Oracle TM

Lecture 26 - NP^NP and #SAT

Lecture 27 - Counting Classes #P and PP

Lecture 28 - Permanent and its Cycle cover of a Graph

Lecture 29 - #P-Complete: Graph Gadgets

Lecture 30 - #P-Hard: Analyse XOR

Lecture 31 - Valient-Vazirani Lemma and Hashing

Lecture 32 - SAT to Parity-SAT

Lecture 33 - Parity Quantification

Lecture 34 - Randomized Reduction of PH to Parity-P

Lecture 35 - PH to #P

Lecture 36 - Probabilistic TM

Lecture 37 - Example of PTM and Introduction to RP and ZPP

Lecture 38 - ZPP = RP and coRP

Lecture 39 - Probability Amplification

Lecture 40 - BPP in PH

Lecture 41 - GNI is in BP.NP

Lecture 42 - GI is NP-hard

Lecture 43 - GI is NP-hard (Continued...) Going Beyond TMs

Lecture 44 - Circuit Complexity

Lecture 45 - TM with Advice - P/poly

Lecture 46 - Circuits for NP and EXP

Lecture 47 - Parallel Computation

Lecture 48 - P-completeness and NEXP-completeness