Search for tag: "reductions"

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

From  David Doty 0 likes 18 plays 0  

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

From  David Doty 0 likes 18 plays 0  

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

From  David Doty 0 likes 63 plays 0  

ECS 220 2b:5.1 NP-completeness and reductions

From  David Doty 0 likes 47 plays 0  

ECS 120 9a:2 reducibility

From  David Doty 0 likes 143 plays 0  

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

From  David Doty 0 likes 95 plays 0  

ECS 120 8c:3 definition of NP-completeness

From  David Doty 0 likes 138 plays 0  

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

From  David Doty 0 likes 102 plays 0  

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

From  David Doty 0 likes 108 plays 0