Course10610622963 lectures

Computational Complexity

Prof. Subrahmanyam Kalyanasundaram · IIT Hyderabad

About

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

Week 1

Week 2

Week 3

Week 4

Week 5

Week 6

Week 7

Week 8

Week 9

Week 10

Week 11

Week 12

Syllabus and materials

At NPTEL, as the course publishes them.

Syllabus

Credits and licence

Institution: IIT Hyderabad
Department: Computer Science and Engineering
Teacher: Prof. Subrahmanyam Kalyanasundaram
Level: Graduate
Language: English
Subjects: Computer science, Engineering
Source: NPTEL
Licence: CC BY-NC-SA, as NPTEL states it. Non-commercial use only. NPTEL's terms
Attribution: NPTEL states: "Distributed under Creative Commons Attribution-ShareAlike / CC BY - NC - SA", beside a BY-NC-SA badge. Coordinated by IIT Madras.
Who can watch: NPTEL gives no rating. Invisible Network shows it to Tweens profiles and older, judged from what the source says about it. How courses are placed