wiki_research

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

nc (612B)

      1 # NC
      2 
      3 "Nick's class"
      4 
      5 understood as meaning that a problem is efficiently parallelizable [parallelization]
      6 
      7 NCi: class of [formal_language] accepted by uniform [boolean_circuit] with polynomial number of gates, maximum [fan_in] 2, and depth O(log^i n)
      8 
      9 It is not known whether the NC hierarchy is proper: if it is not, then it leads to a collapse
     10 
     11 - [barringtons_theorem]: the class BWBP of [regular_language] on {0, 1} that can be recognized with branching programs of polynomial length and bounded width is exactly "nonuniform [nc1]"
     12 
     13 It is assumed but unknown that [nc] neq [ptime]
     14 
     15 - [nc0]
     16 - [nc1]
     17 
     18 Up: [ac]