Search for tag: "reductions"

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

From  David Doty 0 likes 28 plays 0  

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

From  David Doty 0 likes 23 plays 0  

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

From  David Doty 0 likes 110 plays 0  

ECS 220 2b:5.1 NP-completeness and reductions

From  David Doty 0 likes 57 plays 0  

ECS 120 9a:2 reducibility

From  David Doty 0 likes 210 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 140 plays 0  

ECS 120 8c:3 definition of NP-completeness

From  David Doty 0 likes 206 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 146 plays 0  

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

From  David Doty 0 likes 162 plays 0