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

  1. Lecture 1(a): Introduction
  2. Lecture 1(b): Outline
  3. Lecture 2(a): Formalize problems and machine
  4. Lecture 2(b): Turing Machine
  5. Lecture 3(a): Asymptotics, Church-Turing thesis, and UTM
  6. Lecture 3(b): Halting problem and Diagonalization
  7. Lecture 4(a); Classes P, NP, EXP
  8. Lecture 4(b): Comparison of classes and Non-determinism
  9. Lecture 5(a): NP vs Ntime
  10. Lecture 5(b): SAT is NP-hard.
  11. Lecture 6(a): Cook-Levin Theorem.
  12. Lecture 6(b): NP-hardness and Co-Classes
  13. Lecture 7(a): NEXP and Gödel's computation question
  14. Lecture 7(b): Time, Space hierarchy
  15. Lecture 8(a): NDTM hierarchy
  16. Lecture 8(b): Ladner's Theorem and Introduction to Oracles
  17. Lecture 9(a): Oracle and Relativizing proofs.
  18. Lecture 9(b): Non-relativizing P≠NP and Introduction to Space complexity
  19. Lecture 10(a): PSPACE completeness
  20. Lecture 10(b): QBF game and NSpace
  21. Lecture 11(a): NL complete
  22. Lecture 11(b): NL=coNL
  23. Lecture 12(a): Polynomial Hierarchy
  24. Lecture 12(b): PH Conjecture
  25. Lecture 13(a): PH-complete and Oracle TM
  26. Lecture 13(b): NP^NP and #SAT
  27. Lecture 14(a): Counting classes #P and PP
  28. Lecture 14(b): Permanent and its connection to the cycle cover of a Graph
  29. Lecture 15(a): #P-complete: Graph gadgets
  30. Lecture 15(b): #P-hard: Analyse XOR
  31. Lecture 16(a): Valiant-Vazirani Lemma and Hashing
  32. Lecture 16(b): SAT to Parity-SAT
  33. Lecture 17(a): Parity Quantification
  34. Lecture 17(b): Randomized reduction of PH to Parity-P
  35. Lecture 18(a): PH to #P
  36. Lecture 18(b): Probabilistic TM
  37. Lecture 19(a): Example of PTM and Introduction to RP and ZPP
  38. Lecture 19(b): ZPP = RP & coRP
  39. Lecture 20(a): Probability Amplification
  40. Lecture 20(b): BPP in PH
  41. Lecture 21(a): GNI is in BP.NP
  42. Lecture 21(b): GI is NP-hard.
  43. Lecture 22(a): GI is NP-hard continued. Going Beyond TMs
  44. Lecture 22(b): Circuit Complexity
  45. Lecture 23(a): TM with Advice - P/poly.
  46. Lecture 23(b): Circuits for NP and EXP
  47. Lecture 24(a): Parallel Computation.
  48. Lecture 24(b): P-completeness and NEXP-completeness
  49. 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