Search for tag: "a."

Constructing the Pentagon Part 4: The Golden Ratio

From  Joseph Biello 0 likes 0 plays 0  

Constructing the Pentagon Part 3: Angle properties

From  Joseph Biello 0 likes 1 plays 0  

2021-11-17: Approximate Graver-best augmentation, Steinitz bound

Videos and all other materials are copyright 2021 Matthias Köppe and shared as Open Educational Resources subject to the Creative Commons Attribution-ShareAlike 3.0 Unported (CC BY-SA 3.0)…

From  Matthias Koeppe 0 likes 3 plays 0  

ECS 220 7a:7.6-1 counter machine definition and examples

From  David Doty 0 likes 29 plays 0  

ECS 220 5b:6.6-4 two lemmas and full proof of Ladner_s theorem

From  David Doty 0 likes 17 plays 0  

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

From  David Doty 0 likes 17 plays 0  

ECS 220 5b:6.6-1 Ladner's theorem, existence of NP-intermediate problems

From  David Doty 0 likes 24 plays 0  

ECS 220 5a:6.4-4 an oracle making P=NP

From  David Doty 0 likes 24 plays 0  

ECS 220 5a:6.4-3 relativizing proofs

From  David Doty 0 likes 22 plays 0  

ECS 120 10b:2 the real numbers are uncountable and the Continuum Hypothesis

From  David Doty 0 likes 68 plays 0  

ECS 120 9c:2 N vs. Z

From  David Doty 0 likes 97 plays 0  

ECS 120 9b:1 acceptance problem is undecidable

From  David Doty 0 likes 179 plays 0  

ECS 120 9a:1 halting problem definition and Turing-recognizability

From  David Doty 0 likes 147 plays 0  

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

From  David Doty 0 likes 108 plays 0  

ECS 120 8b:3 using reductions to bound hardness of problems

From  David Doty 0 likes 125 plays 0  

ECS 120 8b:2 definition of polynomial-time reducibility

Errata: starting at 8:30, I show Python code with the function reduction_from_clique_to_independent_set. This should be reduction_from_independent_set_to_clique instead.

From  David Doty 0 likes 158 plays 0