logspace (490B)
1 # L 2 3 Class of problems that can be solved with logarithmic [complexity_space] 4 5 Is included in [PTIME] 6 7 Variant [polyl]: solved with [polylogarithmic] [complexity_space] 8 9 Variant [NL] ([nondeterminism]) 10 11 Variant [SL]: symmetric logspace, class of problems reducible to [undirected_reachability], showed to be equal to [logspace] by [reingold] 12 - for [2sat] corresponds to the case where exactly one literal in each clause must hold 13 14 Up: [complexity_class] 15 16 Aliases: L, deterministic logspace