# Basics of Computational Complexity

- Institution: IIT Kanpur
- Department: Computer Science and Engineering
- Teacher: Prof. Nitin Saxena
- Level: Undergraduate
- Language: English
- Subjects: Computer science, Engineering
- Source: [NPTEL](https://nptel.ac.in/courses/106104357)
- Licence: [CC BY-NC-SA](https://nptel.ac.in/faq) (Non-commercial use only.)
- Syllabus: [at the source](https://nptel.ac.in/courses/106104357)
- Who can watch: Tweens profiles and older (sources give no ratings; placed by Invisible Network from the source's own words)

## Lectures

1. [Lecture 1(a): Introduction](https://invisiblenetwork.ai/learn/nptel/106104357/2465fbcd62d9) (Video)
2. [Lecture 1(b): Outline](https://invisiblenetwork.ai/learn/nptel/106104357/a25e0c2156cf) (Video)
3. [Lecture 2(a): Formalize problems and machine](https://invisiblenetwork.ai/learn/nptel/106104357/ce9823938803) (Video)
4. [Lecture 2(b): Turing Machine](https://invisiblenetwork.ai/learn/nptel/106104357/e48bb2b993d1) (Video)
5. [Lecture 3(a): Asymptotics, Church-Turing thesis, and UTM](https://invisiblenetwork.ai/learn/nptel/106104357/29e39e65e346) (Video)
6. [Lecture 3(b): Halting problem and Diagonalization](https://invisiblenetwork.ai/learn/nptel/106104357/9dc4c979db73) (Video)
7. [Lecture 4(a); Classes P, NP, EXP](https://invisiblenetwork.ai/learn/nptel/106104357/52d80030e752) (Video)
8. [Lecture 4(b): Comparison of classes and Non-determinism](https://invisiblenetwork.ai/learn/nptel/106104357/5f3b8eff2f15) (Video)
9. [Lecture 5(a): NP vs Ntime](https://invisiblenetwork.ai/learn/nptel/106104357/31e63128985e) (Video)
10. [Lecture 5(b): SAT is NP-hard.](https://invisiblenetwork.ai/learn/nptel/106104357/13ea8f0d750e) (Video)
11. [Lecture 6(a): Cook-Levin Theorem.](https://invisiblenetwork.ai/learn/nptel/106104357/85e14f6af078) (Video)
12. [Lecture 6(b): NP-hardness and Co-Classes](https://invisiblenetwork.ai/learn/nptel/106104357/c23facb4149d) (Video)
13. [Lecture 7(a): NEXP and Gödel's computation question](https://invisiblenetwork.ai/learn/nptel/106104357/430c281e6486) (Video)
14. [Lecture 7(b): Time, Space hierarchy](https://invisiblenetwork.ai/learn/nptel/106104357/5454ff322b11) (Video)
15. [Lecture 8(a): NDTM hierarchy](https://invisiblenetwork.ai/learn/nptel/106104357/699832003d6a) (Video)
16. [Lecture 8(b): Ladner's Theorem and Introduction to Oracles](https://invisiblenetwork.ai/learn/nptel/106104357/e794690d0376) (Video)
17. [Lecture 9(a): Oracle and Relativizing proofs.](https://invisiblenetwork.ai/learn/nptel/106104357/1d2ba47f46f0) (Video)
18. [Lecture 9(b): Non-relativizing P≠NP and Introduction to Space complexity](https://invisiblenetwork.ai/learn/nptel/106104357/bb3d41a9cb57) (Video)
19. [Lecture 10(a): PSPACE completeness](https://invisiblenetwork.ai/learn/nptel/106104357/f810248a0e98) (Video)
20. [Lecture 10(b): QBF game and NSpace](https://invisiblenetwork.ai/learn/nptel/106104357/d753d45315d0) (Video)
21. [Lecture 11(a): NL complete](https://invisiblenetwork.ai/learn/nptel/106104357/261d1c77a383) (Video)
22. [Lecture 11(b): NL=coNL](https://invisiblenetwork.ai/learn/nptel/106104357/4ad522ad79b8) (Video)
23. [Lecture 12(a): Polynomial Hierarchy](https://invisiblenetwork.ai/learn/nptel/106104357/877832fba435) (Video)
24. [Lecture 12(b): PH Conjecture](https://invisiblenetwork.ai/learn/nptel/106104357/a03025d66a04) (Video)
25. [Lecture 13(a): PH-complete and Oracle TM](https://invisiblenetwork.ai/learn/nptel/106104357/03935deceddd) (Video)
26. [Lecture 13(b): NP^NP and #SAT](https://invisiblenetwork.ai/learn/nptel/106104357/5dd3c33a4702) (Video)
27. [Lecture 14(a): Counting classes #P and PP](https://invisiblenetwork.ai/learn/nptel/106104357/16ad70ff5fea) (Video)
28. [Lecture 14(b): Permanent and its connection to the cycle cover of a Graph](https://invisiblenetwork.ai/learn/nptel/106104357/48f8dca52ea7) (Video)
29. [Lecture 15(a): #P-complete: Graph gadgets](https://invisiblenetwork.ai/learn/nptel/106104357/096ebe25a1d4) (Video)
30. [Lecture 15(b): #P-hard: Analyse XOR](https://invisiblenetwork.ai/learn/nptel/106104357/e02596c1f19d) (Video)
31. [Lecture 16(a): Valiant-Vazirani Lemma and Hashing](https://invisiblenetwork.ai/learn/nptel/106104357/184f9713a812) (Video)
32. [Lecture 16(b): SAT to Parity-SAT](https://invisiblenetwork.ai/learn/nptel/106104357/cc8712d323b1) (Video)
33. [Lecture 17(a): Parity Quantification](https://invisiblenetwork.ai/learn/nptel/106104357/1e03c7ca588f) (Video)
34. [Lecture 17(b): Randomized reduction of PH to Parity-P](https://invisiblenetwork.ai/learn/nptel/106104357/dbd37b52c2c3) (Video)
35. [Lecture 18(a): PH to #P](https://invisiblenetwork.ai/learn/nptel/106104357/351ab23c375a) (Video)
36. [Lecture 18(b): Probabilistic TM](https://invisiblenetwork.ai/learn/nptel/106104357/c5b48430182d) (Video)
37. [Lecture 19(a): Example of PTM and Introduction to RP and ZPP](https://invisiblenetwork.ai/learn/nptel/106104357/7ea389d2a188) (Video)
38. [Lecture 19(b): ZPP = RP & coRP](https://invisiblenetwork.ai/learn/nptel/106104357/2d937e66e108) (Video)
39. [Lecture 20(a): Probability Amplification](https://invisiblenetwork.ai/learn/nptel/106104357/a3f3f09e881a) (Video)
40. [Lecture 20(b): BPP in PH](https://invisiblenetwork.ai/learn/nptel/106104357/78e395d2d07f) (Video)
41. [Lecture 21(a): GNI is in BP.NP](https://invisiblenetwork.ai/learn/nptel/106104357/a00b66ccca2c) (Video)
42. [Lecture 21(b): GI is NP-hard.](https://invisiblenetwork.ai/learn/nptel/106104357/de8401f2f06f) (Video)
43. [Lecture 22(a): GI is NP-hard continued. Going Beyond TMs](https://invisiblenetwork.ai/learn/nptel/106104357/cdaaeea99902) (Video)
44. [Lecture 22(b): Circuit Complexity](https://invisiblenetwork.ai/learn/nptel/106104357/2628d4532ba1) (Video)
45. [Lecture 23(a): TM with Advice - P/poly.](https://invisiblenetwork.ai/learn/nptel/106104357/799aed92ab9e) (Video)
46. [Lecture 23(b): Circuits for NP and EXP](https://invisiblenetwork.ai/learn/nptel/106104357/936f817688e8) (Video)
47. [Lecture 24(a): Parallel Computation.](https://invisiblenetwork.ai/learn/nptel/106104357/2d873df28a73) (Video)
48. [Lecture 24(b): P-completeness and NEXP-completeness](https://invisiblenetwork.ai/learn/nptel/106104357/a8f54febbc4d) (Video)
49. [Live Session 13-02-2024](https://invisiblenetwork.ai/learn/nptel/106104357/2465fbcd62d9-2) (Video)