# Computational Complexity - Institution: IIT Hyderabad - Department: Computer Science and Engineering - Teacher: Prof. Subrahmanyam Kalyanasundaram - Level: Graduate - Language: English - Subjects: Computer science, Engineering - Source: [NPTEL](https://nptel.ac.in/courses/106106229) - Licence: [CC BY-NC-SA](https://nptel.ac.in/faq) (Non-commercial use only.) - Syllabus: [at the source](https://nptel.ac.in/courses/106106229) - Who can watch: Tweens profiles and older (sources give no ratings; placed by Invisible Network from the source's own words) This course is an introduction to the area of computational complexity theory. We will see different models of computations and computational complexity classes. The computational models measure various different aspects of computation, like time, space, randomness, number of gates, amount of communication etc. The complexity classes classify different computational problems depending on their easiness or hardness as per these different models. We will also see how these complexity classes are related to each other. Many of the results are extremely interesting and use several interesting ideas. Intended audience: Students of Computer Science discipline. This could be BTech students who are interested in Theory or MTech/PhD students. Prerequisites: Theory of Computation. ## Lectures 1. [Introduction to Computational Complexity](https://invisiblenetwork.ai/learn/nptel/106106229/9c8d7988a6da) (YouTube) 2. [The Class P](https://invisiblenetwork.ai/learn/nptel/106106229/9725c035ab4d) (YouTube) 3. [The Class NP](https://invisiblenetwork.ai/learn/nptel/106106229/88d858624c3a) (YouTube) 4. [The Class NP - Alternate Definition](https://invisiblenetwork.ai/learn/nptel/106106229/1094f1030a73) (YouTube) 5. [Polynomial Time Reductions](https://invisiblenetwork.ai/learn/nptel/106106229/f2ce95fbd44d) (YouTube) 6. [NP - Completeness](https://invisiblenetwork.ai/learn/nptel/106106229/2064e94dbb8f) (YouTube) 7. [Cook Levin Theorem: Part 1](https://invisiblenetwork.ai/learn/nptel/106106229/3edb88987b0f) (YouTube) 8. [Cook Levin Theorem: Part 2](https://invisiblenetwork.ai/learn/nptel/106106229/12307d01b683) (YouTube) 9. [More NP Complete Problems](https://invisiblenetwork.ai/learn/nptel/106106229/7de95805bd31) (YouTube) 10. [Polynomial Hierarchy: Part 1](https://invisiblenetwork.ai/learn/nptel/106106229/bce82a1e9fe2) (YouTube) 11. [Polynomial Hierarchy: Part 2](https://invisiblenetwork.ai/learn/nptel/106106229/ccf270d005c8) (YouTube) 12. [Polynomial Hierarchy: Part 3](https://invisiblenetwork.ai/learn/nptel/106106229/c9699d2cf653) (YouTube) 13. [Time Hierarchy Theorem](https://invisiblenetwork.ai/learn/nptel/106106229/dfa341c12e86) (YouTube) 14. [Introduction to Space Complexity](https://invisiblenetwork.ai/learn/nptel/106106229/bc99d75a3c5d) (YouTube) 15. [NL-Completeness](https://invisiblenetwork.ai/learn/nptel/106106229/4d39f6db7c5d) (YouTube) 16. [Savitch's Theorem](https://invisiblenetwork.ai/learn/nptel/106106229/fcda9f1bcf7c) (YouTube) 17. [NL = co-NL: Part 1](https://invisiblenetwork.ai/learn/nptel/106106229/a251e8b62743) (YouTube) 18. [NL = co-NL: Part 2](https://invisiblenetwork.ai/learn/nptel/106106229/1d91c0f35a3a) (YouTube) 19. [PSPACE Completeness](https://invisiblenetwork.ai/learn/nptel/106106229/01617cd24c03) (YouTube) 20. [Games and PSPACE Completeness](https://invisiblenetwork.ai/learn/nptel/106106229/4798771f442c) (YouTube) 21. [Space Hierarchy Theorem](https://invisiblenetwork.ai/learn/nptel/106106229/73645d068d05) (YouTube) 22. [Ladner's Theorem](https://invisiblenetwork.ai/learn/nptel/106106229/9fbb13e27df4) (YouTube) 23. [Oracle Turing Machines](https://invisiblenetwork.ai/learn/nptel/106106229/6162f5e83f43) (YouTube) 24. [Polynomial Hierarchy Using Oracles](https://invisiblenetwork.ai/learn/nptel/106106229/f09bda25f91c) (YouTube) 25. [Baker-Gill-Solovay Theorem: Part 1](https://invisiblenetwork.ai/learn/nptel/106106229/1d8014977576) (YouTube) 26. [Baker-Gill-Solovay Theorem: Part 2](https://invisiblenetwork.ai/learn/nptel/106106229/9c0e00c44ac6) (YouTube) 27. [Randomized Complexity Classes: Part 1](https://invisiblenetwork.ai/learn/nptel/106106229/3680cdb42fd5) (YouTube) 28. [Randomized Complexity Classes: Part 2](https://invisiblenetwork.ai/learn/nptel/106106229/60315ae60da8) (YouTube) 29. [Randomized Complexity Classes: Part 3](https://invisiblenetwork.ai/learn/nptel/106106229/cfb7b4a7b563) (YouTube) 30. [Randomized Complexity Classes: Part 4](https://invisiblenetwork.ai/learn/nptel/106106229/06cc0a9c9c67) (YouTube) 31. [Comparison Between Randomized Complexity Classes](https://invisiblenetwork.ai/learn/nptel/106106229/6316a8e3464d) (YouTube) 32. [BPP is in Polynomial Hierarchy](https://invisiblenetwork.ai/learn/nptel/106106229/ef123e199781) (YouTube) 33. [Circuit Complexity: Part 1](https://invisiblenetwork.ai/learn/nptel/106106229/929e05dcc77c) (YouTube) 34. [Circuit Complexity: Part 2](https://invisiblenetwork.ai/learn/nptel/106106229/e3238823530b) (YouTube) 35. [Formal Definition of Circuits](https://invisiblenetwork.ai/learn/nptel/106106229/81787ba3365f) (YouTube) 36. [Hierarchy Theorem for Circuit Size](https://invisiblenetwork.ai/learn/nptel/106106229/a00a25656cc9) (YouTube) 37. [Complexity Class : P/Poly](https://invisiblenetwork.ai/learn/nptel/106106229/e9202b06a5ad) (YouTube) 38. [Karp-Lipton Theorem](https://invisiblenetwork.ai/learn/nptel/106106229/e24bee56e55c) (YouTube) 39. [Turing Machines That Take Advice](https://invisiblenetwork.ai/learn/nptel/106106229/7418496dfc6c) (YouTube) 40. [Classes NC and AC](https://invisiblenetwork.ai/learn/nptel/106106229/f810d54e17c9) (YouTube) 41. [Parity Not in AC0: Part 1](https://invisiblenetwork.ai/learn/nptel/106106229/4bbbbddecaa3) (YouTube) 42. [Parity Not in AC0: Part 2](https://invisiblenetwork.ai/learn/nptel/106106229/b39093a02680) (YouTube) 43. [Adleman's Theorem](https://invisiblenetwork.ai/learn/nptel/106106229/59f4d1941990) (YouTube) 44. [Polynomial Identity Testing and Bipartite Perfect Matching in RNC](https://invisiblenetwork.ai/learn/nptel/106106229/ba24917ce965) (YouTube) 45. [Search Bipartite Perfect Matching is in RNC: Part 1](https://invisiblenetwork.ai/learn/nptel/106106229/c704f5b8184d) (YouTube) 46. [Search Bipartite Perfect Matching is in RNC: Part 2](https://invisiblenetwork.ai/learn/nptel/106106229/5e25da79a007) (YouTube) 47. [Promise Problems and Valiant-Vazirani Theorem](https://invisiblenetwork.ai/learn/nptel/106106229/318c7795aa9b) (YouTube) 48. [Valiant Vazirani Theorem Continued](https://invisiblenetwork.ai/learn/nptel/106106229/e81de1c441b9) (YouTube) 49. [#P and the Complexity of Counting](https://invisiblenetwork.ai/learn/nptel/106106229/dfb1196c7ab1) (YouTube) 50. [Permanent is #P-Complete: Part 1](https://invisiblenetwork.ai/learn/nptel/106106229/436ab0d032ad) (YouTube) 51. [Permanent is #P-Complete: Part 2](https://invisiblenetwork.ai/learn/nptel/106106229/fddce3e740de) (YouTube) 52. [Toda's Theorem: Part 1](https://invisiblenetwork.ai/learn/nptel/106106229/176c47051212) (YouTube) 53. [Toda's Theorem: Part 2](https://invisiblenetwork.ai/learn/nptel/106106229/37594ee87a48) (YouTube) 54. [Introduction to Communication Complexity: Part 1](https://invisiblenetwork.ai/learn/nptel/106106229/e9ffe2613c5a) (YouTube) 55. [Introduction to Communication Complexity: Part 2](https://invisiblenetwork.ai/learn/nptel/106106229/ab8722904ddf) (YouTube) 56. [Lower Bound Techniques](https://invisiblenetwork.ai/learn/nptel/106106229/5396a89d7084) (YouTube) 57. [Communication Complexity of Relations](https://invisiblenetwork.ai/learn/nptel/106106229/6b5c6004090d) (YouTube) 58. [Monotone Depth Lower Bound for Matching](https://invisiblenetwork.ai/learn/nptel/106106229/7859cdeefd89) (YouTube) 59. [Interactive Proofs](https://invisiblenetwork.ai/learn/nptel/106106229/09eb0b9b235f) (YouTube) 60. [#3SAT is in IP](https://invisiblenetwork.ai/learn/nptel/106106229/584e88fd77db) (YouTube) 61. [Public Coin Interactive Proofs and AM/MA](https://invisiblenetwork.ai/learn/nptel/106106229/17ff75b60f14) (YouTube) 62. [Simulating Private Coins using Public Coins](https://invisiblenetwork.ai/learn/nptel/106106229/fcff684fac75) (YouTube) 63. [Summary and Concluding Remarks](https://invisiblenetwork.ai/learn/nptel/106106229/2150e48ed48e) (YouTube)