Permanent is #P-Complete: Graduate Complexity Lecture at CMU
Offered By: Ryan O'Donnell via YouTube
Course Description
Overview
Explore the complexity of the permanent problem in this graduate-level lecture on Computational Complexity Theory. Delve into the proof that the permanent is #P-complete, covering topics such as cycle covers, weight reductions, the NAND graph, and Sharp 3SAT. Learn about clause gadgets, consistency checks, and hole reductions as part of the main reduction strategy. Analyze the intricacies of weak identification and edge pair identification in this advanced exploration of computational complexity concepts.
Syllabus
Introduction
Cycle covers
Reducing cycle covers
Reducing weights
Reducing exponentially large weights
The nand graph
Sharp 3sat
Main reduction
Clause gadget
Consistency
Subdividing
Bonus twist
Identifying pairs of edges
Hole reduction
Weak identification
Analysis
Taught by
Ryan O'Donnell
Related Courses
算法设计与分析(高级) | Advanced Design and Analysis of AlgorithmsPeking University via edX 理论计算机科学基础 | Introduction to Theoretical Computer Science
Peking University via edX An Introduction to Algorithmics
Pluralsight The Introduction to Quantum Computing
Saint Petersburg State University via Coursera Computational Complexity
IIT Hyderabad via Swayam