Nick's Class

The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.

Steven Cook's class of those problems decidable in polylogarithmic time on polynomially many processors. A problem is in NC if there exist constants c and k such that it can be solved in time O(lg^c n) using O(n^k) parallel processors.