Search for tag: "reachability"

ECS 220 9b:8.5 Immerman-Szelepcsényi Theorem NSPACE(s(n)) = coNSPACE(s(n)) for s(n) ≥ log(n)

From  David Doty 0 likes 71 plays 0  

ECS 220 8c:8.6-1 Reachability expressed logically, and as a game between prover and skeptic

From  David Doty 0 likes 23 plays 0  

ECS 220 8c:8.4 Savitch's theorem space-bounded deterministic simulation of space-bounded nondeterminism, space usage of Savitch_s algorithm

From  David Doty 0 likes 36 plays 0  

ECS 220 8b:8.3-2 NL-WitnessExistence and Reachability are NL-complete

From  David Doty 0 likes 27 plays 0  

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

From  David Doty 0 likes 36 plays 0  

ECS 220 8b:8.2 Reachability

From  David Doty 0 likes 52 plays 0  

ECS 220 2a:4.2-2 k-SAT for k=1,2,3

From  David Doty 0 likes 77 plays 0