Completed
15. #P and ASP
Class Central Classrooms beta
YouTube videos curated by Class Central.
Classroom Contents
Algorithmic Lower Bounds: Fun with Hardness Proofs
Automatically move to the next video in the Classroom when playback concludes
- 1 1. Overview
- 2 2. 3-Partition I
- 3 3. 3-Partition II
- 4 4. SAT I
- 5 5. SAT Reductions
- 6 6. Circuit SAT
- 7 7. Planar SAT
- 8 8. Hamiltonicity
- 9 9. Graph Problems
- 10 10. Inapproximabililty Overview
- 11 11. Inapproximability Examples
- 12 12. Gaps and PCP
- 13 13. W Hierarchy
- 14 14. ETH and Planar FPT
- 15 15. #P and ASP
- 16 16. NP and PSPACE Video Games
- 17 17. Nondeterministic Constraint Logic
- 18 18. 0- and 2-Player Games
- 19 19. Unbounded Games
- 20 20. Undecidable and P-Complete
- 21 21. 3SUM and APSP Hardness
- 22 22. PPAD
- 23 23. PPAD Reductions