Lecture 35 of 37Parallel Complexity Theory
Circuit Value Problem is P-complete for NC-reductions
Prof. Sajith Gopalan · IIT Guwahati
Credits and licence
- From
- Parallel Algorithms, IIT Guwahati (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.
- Who can watch
- Tweens profiles and older. How courses are placed
All the lectures
- Shared Memory Models - 1
- Shared Memory Models - 2
- Interconnection Networks
- Cost and Optimality
- Basic Techniques 1
- Basic Techniques 2
- Basic Techniques 3
- Basic Techniques 4
- Basic Techniques 5
- Odd Even Merge Sort (OEMS)
- OEMS, Bitonic-Sort-Merge Sort (BSMS)
- BSMS, Optimal List Colouring
- Description
- Analysis
- Applications
- Applications
- Fast optimal merge algorithm
- High level Description
- Cole's Merge Sort: Details
- Analysis of Cole's Merge Sort; Lower bound for sorting
- Sorting Lower bound; Connected Components
- Connected Components (CREW)
- Connected Components, Vertex Colouring
- Sorting on a 2D mesh
- Sorting on a 2D mesh
- Sorting, Offline routing on a 2D mesh
- Sorting on a 3D mesh
- Mesh of Trees, Hypercube
- Hypercube cont'd
- Hypercube cont'd, butterfly network
- Butterfly, CCC and Benes Networks
- Butterfly, CCC and Benes Networks
- Shuffle Exchange Graphs, de Bruijn Graphs
- Interconnection Networks Algorithms
- Circuit Value Problem is P-complete for NC-reductions
- Ordered DFS is P-complete for NC-reductions
- Max Flow is P-complete for NC-reductions