wiki_research

personal research wiki
git clone https://a3nm.net/git/wiki_research/
Log | Files | Refs

nlogspace (504B)

      1 # NL
      2 
      3 [complexity_class] of [decision_problem] that can be solved by [nondeterministic] [turing_machine] with [logarithm] amount of memory
      4 
      5 Like [logspace] with [nondeterministic]
      6 
      7 Complete problems:
      8 
      9 - directed [reachability]
     10 - [2sat]
     11 
     12 Known to be equal to [co-NL]: the Immerman–Szelepcsényi theorem [immerman_szelepcsenyi_theorem]
     13 
     14 [descriptive_complexity]: corresponds to [fotc] = [first_order_logic] with [transitive_closure] operator
     15 
     16 Up: [complexity_class]
     17 
     18 See also: [nl_complete]
     19 
     20 Aliases: NL