Learn · Computational Complexity
Lecture 46 of 63Week 9
Search Bipartite Perfect Matching is in RNC: Part 2
Prof. Subrahmanyam Kalyanasundaram · IIT Hyderabad
Credits and licence
- From
- Computational Complexity, IIT Hyderabad (at NPTEL)
- Licence
- CC BY-NC-SA, as NPTEL states it. Non-commercial use only.
- 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
- Tweens profiles and older. How courses are placed
All the lectures
- Introduction to Computational Complexity
- The Class P
- The Class NP
- The Class NP - Alternate Definition
- Polynomial Time Reductions
- NP - Completeness
- Cook Levin Theorem: Part 1
- Cook Levin Theorem: Part 2
- More NP Complete Problems
- Polynomial Hierarchy: Part 1
- Polynomial Hierarchy: Part 2
- Polynomial Hierarchy: Part 3
- Time Hierarchy Theorem
- Introduction to Space Complexity
- NL-Completeness
- Savitch's Theorem
- NL = co-NL: Part 1
- NL = co-NL: Part 2
- PSPACE Completeness
- Games and PSPACE Completeness
- Space Hierarchy Theorem
- Ladner's Theorem
- Oracle Turing Machines
- Polynomial Hierarchy Using Oracles
- Baker-Gill-Solovay Theorem: Part 1
- Baker-Gill-Solovay Theorem: Part 2
- Randomized Complexity Classes: Part 1
- Randomized Complexity Classes: Part 2
- Randomized Complexity Classes: Part 3
- Randomized Complexity Classes: Part 4
- Comparison Between Randomized Complexity Classes
- BPP is in Polynomial Hierarchy
- Circuit Complexity: Part 1
- Circuit Complexity: Part 2
- Formal Definition of Circuits
- Hierarchy Theorem for Circuit Size
- Complexity Class : P/Poly
- Karp-Lipton Theorem
- Turing Machines That Take Advice
- Classes NC and AC
- Parity Not in AC0: Part 1
- Parity Not in AC0: Part 2
- Adleman's Theorem
- Polynomial Identity Testing and Bipartite Perfect Matching in RNC
- Search Bipartite Perfect Matching is in RNC: Part 1
- Search Bipartite Perfect Matching is in RNC: Part 2
- Promise Problems and Valiant-Vazirani Theorem
- Valiant Vazirani Theorem Continued
- #P and the Complexity of Counting
- Permanent is #P-Complete: Part 1
- Permanent is #P-Complete: Part 2
- Toda's Theorem: Part 1
- Toda's Theorem: Part 2
- Introduction to Communication Complexity: Part 1
- Introduction to Communication Complexity: Part 2
- Lower Bound Techniques
- Communication Complexity of Relations
- Monotone Depth Lower Bound for Matching
- Interactive Proofs
- #3SAT is in IP
- Public Coin Interactive Proofs and AM/MA
- Simulating Private Coins using Public Coins
- Summary and Concluding Remarks