NC (complexity)
id:
nc-complexity-187-11926995
title:
NC (complexity)
text:
In computational complexity theory, the class NC 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 O(c) using O(nk) 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
brand slug:
wiki
category slug:
encyclopedia
description:
original url:
https://en.wikipedia.org/wiki/NC_(complexity)
date created:
2002-01-01T02:15:54Z
date modified:
2024-09-08T17:25:53Z
main entity:
{"identifier":"Q1141840","url":"https://www.wikidata.org/entity/Q1141840"}
image:
fields total:
13
integrity:
14