IIT Kanpur · Computer Science
Basics of Computational Complexity
Prof. Nitin Saxena · 49 free video lectures
49 video lectures. Topics: (a): Introduction; (b): Outline; (a): Formalize problems and machine; (b): Turing Machine; (a): Asymptotics, Church-Turing thesis, and UTM; (b): Halting problem and Diagonalization; (a); Classes P, NP, EXP; (b): Comparison of classes and Non-determinism; (a): NP vs Ntime…
▶ Play on Open Lecture HallCourse page ↗
Lectures
- Lecture 1(a): Introduction
- Lecture 1(b): Outline
- Lecture 2(a): Formalize problems and machine
- Lecture 2(b): Turing Machine
- Lecture 3(a): Asymptotics, Church-Turing thesis, and UTM
- Lecture 3(b): Halting problem and Diagonalization
- Lecture 4(a); Classes P, NP, EXP
- Lecture 4(b): Comparison of classes and Non-determinism
- Lecture 5(a): NP vs Ntime
- Lecture 5(b): SAT is NP-hard.
- Lecture 6(a): Cook-Levin Theorem.
- Lecture 6(b): NP-hardness and Co-Classes
- Lecture 7(a): NEXP and Gödel's computation question
- Lecture 7(b): Time, Space hierarchy
- Lecture 8(a): NDTM hierarchy
- Lecture 8(b): Ladner's Theorem and Introduction to Oracles
- Lecture 9(a): Oracle and Relativizing proofs.
- Lecture 9(b): Non-relativizing P≠NP and Introduction to Space complexity
- Lecture 10(a): PSPACE completeness
- Lecture 10(b): QBF game and NSpace
- Lecture 11(a): NL complete
- Lecture 11(b): NL=coNL
- Lecture 12(a): Polynomial Hierarchy
- Lecture 12(b): PH Conjecture
- Lecture 13(a): PH-complete and Oracle TM
- Lecture 13(b): NP^NP and #SAT
- Lecture 14(a): Counting classes #P and PP
- Lecture 14(b): Permanent and its connection to the cycle cover of a Graph
- Lecture 15(a): #P-complete: Graph gadgets
- Lecture 15(b): #P-hard: Analyse XOR
- Lecture 16(a): Valiant-Vazirani Lemma and Hashing
- Lecture 16(b): SAT to Parity-SAT
- Lecture 17(a): Parity Quantification
- Lecture 17(b): Randomized reduction of PH to Parity-P
- Lecture 18(a): PH to #P
- Lecture 18(b): Probabilistic TM
- Lecture 19(a): Example of PTM and Introduction to RP and ZPP
- Lecture 19(b): ZPP = RP & coRP
- Lecture 20(a): Probability Amplification
- Lecture 20(b): BPP in PH
- Lecture 21(a): GNI is in BP.NP
- Lecture 21(b): GI is NP-hard.
- Lecture 22(a): GI is NP-hard continued. Going Beyond TMs
- Lecture 22(b): Circuit Complexity
- Lecture 23(a): TM with Advice - P/poly.
- Lecture 23(b): Circuits for NP and EXP
- Lecture 24(a): Parallel Computation.
- Lecture 24(b): P-completeness and NEXP-completeness
- Live Session 13-02-2024
From NPTEL (IITs and IISc) · CC BY-NC-SA. More from IIT Kanpur.
Open Lecture Hall is free, with no ads and no sign-up. It is not run by or connected to any university; the lectures are the universities' own free recordings, played from where they host them. About & rights