What you will learn
-
Computer Science and Engineering
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.
mod01lec01 - Introduction to Computational Complexity
Preview
35:23
mod01lec02 - The Class P
Preview
27:04
mod01lec03 - The Class NP
Preview
41:14
mod01lec04 - The Class NP - Alternate Definition
Preview
39:06
mod01lec05 - Polynomial Time Reductions
Preview
43:04
mod01lec06 - NP - Completeness
Preview
12:00
mod02lec07 - Cook Levin Theorem: Part 1
Preview
36:35
mod02lec08 - Cook Levin Theorem: Part 2
Preview
33:25
mod02lec09 - More NP Complete Problems
Preview
35:49
mod02lec10 - Polynomial Hierarchy: Part 1
Preview
19:49
mod02lec11 - Polynomial Hierarchy: Part 2
Preview
35:22
mod02lec12 - Polynomial Hierarchy: Part 3
Preview
24:05
mod04lec19 - PSPACE Completeness
Preview
46:26
mod04lec20 - Games and PSPACE Completeness
Preview
30:02
mod04lec21 - Space Hierarchy Theorem
Preview
32:56
mod04lec22 - Ladner's Theorem
Preview
20:30
mod04lec23 - Oracle Turing Machines
Preview
24:38
mod04lec24 - Polynomial Hierarchy Using Oracles
Preview
28:56
mod05lec25 - Baker-Gill-Solovay Theorem: Part 1
Preview
28:58
mod05lec26 - Baker-Gill-Solovay Theorem: Part 2
Preview
30:15
mod05lec27 - Randomized Complexity Classes: Part 1
Preview
35:01
mod05lec28 - Randomized Complexity Classes: Part 2
Preview
44:27
mod05lec29 - Randomized Complexity Classes: Part 3
Preview
38:22
mod06lec30 - Randomized Complexity Classes: Part 4
Preview
37:11
mod06lec31 - Comparison Between Randomized Complexity Classes
Preview
11:20
mod06lec32 - BPP is in Polynomial Hierarchy
Preview
44:25
mod06lec33 - Circuit Complexity: Part 1
Preview
33:17
mod06lec34 - Circuit Complexity: Part 2
Preview
30:11
mod07lec35 - Formal Definition of Circuits
Preview
28:39
mod07lec36 - Hierarchy Theorem for Circuit Size
Preview
29:43
mod07lec37 - Complexity Class : P/Poly
Preview
24:03
mod07lec38 - Karp-Lipton Theorem
Preview
51:59
mod07lec39 - Turing Machines That Take Advice
Preview
19:36
mod07lec40 - Classes NC and AC
Preview
48:00
mod09lec45 - Search Bipartite Perfect Matching is in RNC: Part 1
Preview
24:28
mod09lec46 - Search Bipartite Perfect Matching is in RNC: Part 2
Preview
27:40
mod09lec47 - Promise Problems and Valiant-Vazirani Theorem
Preview
21:55
mod09lec48 - Valiant Vazirani Theorem Continued
Preview
55:14
mod09lec49 - #P and the Complexity of Counting
Preview
39:19
mod11lec54 - Introduction to Communication Complexity: Part 1
Preview
40:01
mod11lec55 - Introduction to Communication Complexity: Part 2
Preview
47:51
mod11lec56 - Lower Bound Techniques
Preview
35:32
mod11lec57 - Communication Complexity of Relations
Preview
52:07
mod11lec58 - Monotone Depth Lower Bound for Matching
Preview
37:27
No Discussion Found
0.0
0 Reviews
Meet Your Instructor
About Instructor
VTU is one of the largest Technological Universities in India with 24 years of Tradition of excellence in Engineering & Technical Education, Research and Innovations. It came into existence in the year 1998 to cater the needs of Indian industries for trained technical manpower with practical experience and sound theoretical knowledge.
Free
-
Course Duration38 h 46 m 35 s
-
Course LevelIntermediate
-
Student Enrolled59
-
LanguageEnglish
This Course Includes
- 38 h 46 m 35 s Video Lectures
- 2 Quizzes
- 0 Assignments
- 0 Downloadable Resources
- Full Lifetime Access
- Certificate of Completion