wiki_research

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

nc1 (369B)

      1 # NC1
      2 
      3 https://en.wikipedia.org/wiki/NC_(complexity)
      4 
      5 circuits with [polynomial] [circuit_size] and [polylogarithmic] [depth]
      6 
      7 NC1 circuits equivalent to polynomial-size uniform family of [formula_boolean]
      8 
      9 https://en.wikipedia.org/wiki/NL_(complexity) says we have:
     10 
     11 [nc1] included in [logtime] included in [nlogtime] included in [nc2]
     12 
     13 Up: [nc], [circuit_complexity]