Search for tag: "a."

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

From  David Doty 0 likes 17 plays 0  

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

From  David Doty 0 likes 14 plays 0  

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

From  David Doty 0 likes 14 plays 0  

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

From  David Doty 0 likes 18 plays 0  

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

From  David Doty 0 likes 22 plays 0  

ECS 220 5a:6.4-3 relativizing proofs

From  David Doty 0 likes 20 plays 0  

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

From  David Doty 0 likes 52 plays 0  

ECS 120 9c:2 N vs. Z

From  David Doty 0 likes 82 plays 0  

ECS 120 9b:1 acceptance problem is undecidable

From  David Doty 0 likes 149 plays 0  

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

From  David Doty 0 likes 124 plays 0  

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

From  David Doty 0 likes 96 plays 0  

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

From  David Doty 0 likes 111 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 130 plays 0  

ECS 120 8a:5 ranking the hardness of problems

From  David Doty 0 likes 117 plays 0  

ECS 120 4c:3 NFAs with isolated start and accept state

From  David Doty 1 likes 94 plays 0  

ECS 120 4c:2 NFAs can simulate regex_s example

From  David Doty 1 likes 155 plays 0