Algorithmic Lower Bounds, Fall 2014 (Erik Demaine / MIT)

# automatic playing for the 23 videos (click the up-left corner for the list)

source: MIT OpenCourseWare     Last updated on 2015年7月14日
View the complete course: http://ocw.mit.edu/6-890F14
MIT 6.890 Algorithmic Lower Bounds, Fall 2014
In this lecture, Professor Demaine gives a brief overview of the class, summarizing the prerequisite complexity theory and featuring two examples of hardness proofs in games.
License: Creative Commons BY-NC-SA
More information at http://ocw.mit.edu/terms
More courses at http://ocw.mit.edu

1. Overview 1:17:31
2. 3-Partition I 1:23:35
3. 3-Partition II 1:20:58
4. SAT I 1:20:32
5. SAT Reductions 1:21:39
6. Circuit SAT 1:18:40
7. Planar SAT 1:23:03
8. Hamiltonicity 1:21:08
9. Graph Problems 1:20:26
10. Inapproximability Overview 1:18:35
11. Inapproximability Examples 1:20:08
12. Gaps and PCP 1:22:54
13. W Hierarchy 1:21:13
14. ETH and Planar FPT 1:22:49
15. #P and ASP 1:22:36
16. NP and PSPACE Video Games 1:18:17
17. Nondeterministic Constraint Logic 1:20:01
18. 0- and 2-Player Games 1:20:38
19. Unbounded Games 1:22:38
20. Undecidable and P-Complete 1:23:22
21. 3SUM and APSP Hardness 1:19:23
22. PPAD 1:20:48
23. PPAD Reductions 1:23:00