05:39 duration 5 minutes 39 seconds

ECS 220 8b:8.3-1 NL-completeness and logspace…

ECS 220 8b:8.3-1 NL-completeness and logspace reductions

07:35 duration 7 minutes 35 seconds

ECS 220 5b:6.6-2 almost proof of Ladner's…

ECS 220 5b:6.6-2 almost proof of Ladner's theorem

08:40 duration 8 minutes 40 seconds

ECS 220 2c:5.3-1 NAE-SAT is NP-complete

11:09 duration 11 minutes 9 seconds

ECS 220 2b:5.1 NP-completeness and reductions

05:27 duration 5 minutes 27 seconds

ECS 120 9a:2 reducibility

03:43 duration 3 minutes 43 seconds

ECS 120 8c:4 Cook-Levin Theorem if P neq NP, then…

ECS 120 8c:4 Cook-Levin Theorem if P neq NP, then no NP-complete problem is in P

12:07 duration 12 minutes 7 seconds

ECS 120 8c:3 definition of NP-completeness

02:03 duration 2 minutes 3 seconds

ECS 120 8c:2 reduction between two problems is an…

ECS 120 8c:2 reduction between two problems is an algorithm, but it does not solve either problem

02:27 duration 2 minutes 27 seconds

ECS 120 8b:4 how to remember which direction…

ECS 120 8b:4 how to remember which direction reductions go