nc (1011B)
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 recently shown to contain the [bipartite_perfect_matching_problem] 19 - https://blog.computationalcomplexity.org/2026/07/bipartite-perfect-matching-in.html?m=1 20 - an example of [derandomization] as it was known to be in [randomized_NC] 21 22 contains the [det] problem of computing the [determinant] of a [matrix] 23 - cf https://blog.computationalcomplexity.org/2026/07/bipartite-perfect-matching-in.html?m=1 24 25 Up: [ac]