Nick's class

In computational complexity theory [Computational complexity theory], the class NC (for “Nick’s Class”) is the set of decision problems decidable in polylogarithmic time on a parallel computer with a polynomial number of processors. In other words, a problem with input size \(n\) is in NC if there exist constants \(c\) and \(k\) such that it can be solved in time \(\bigo{\log^c n}\) using \(\bigo{n^k}\) parallel processors. Stephen Cook coined the name “Nick’s class” after Nick Pippenger, who had done extensive research on circuits with polylogarithmic depth and polynomial size.

Just as the class P [P (Complexity)] can be thought of as the tractable problems (Cobham’s thesis), so NC can be thought of as the problems that can be efficiently solved on a parallel computer.

(“NC (Complexity)” 2022)

Bibliography