Completed
Sharp 3sat
Class Central Classrooms beta
YouTube videos curated by Class Central.
Classroom Contents
Permanent is #P-Complete: Graduate Complexity Lecture at CMU
Automatically move to the next video in the Classroom when playback concludes
- 1 Introduction
- 2 Cycle covers
- 3 Reducing cycle covers
- 4 Reducing weights
- 5 Reducing exponentially large weights
- 6 The nand graph
- 7 Sharp 3sat
- 8 Main reduction
- 9 Clause gadget
- 10 Consistency
- 11 Subdividing
- 12 Bonus twist
- 13 Identifying pairs of edges
- 14 Hole reduction
- 15 Weak identification
- 16 Analysis
