NC (complexity)
In 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 is in NC if there exist constants c and k such that it can be solved in time O(logc n) 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. RNC is a class extending NC with access to randomness.
Wikipage disambiguates
primaryTopic
NC (complexity)
In 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 is in NC if there exist constants c and k such that it can be solved in time O(logc n) 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. RNC is a class extending NC with access to randomness.
has abstract
En teoría de la complejidad co ...... garítmica y tamaño polinómico.
@es
En théorie de la complexité, u ...... produit matriciel est dans NC.
@fr
In complexity theory, the clas ...... NC with access to randomness.
@en
NC steht in der Informatik als ...... (siehe auch Parallelisierung).
@de
Na teoria da complexidade, a c ...... se com acesso a aleatoriedade.
@pt
Nella teoria della complessità ...... he le ha introdotte per primo.
@it
在计算复杂度理论，NC（Nick's Class），是一个复 ...... EREW都是不受影响的。 RNC是随机化方向的对NC的扩展。
@zh
計算複雑性理論において、NC（Nick's Class）とは ...... n)O(1) 回の交替で解ける決定問題の集合と同じである。
@ja
Link from a Wikipage to an external page
Wikipage page ID
Wikipage revision ID
743,451,984
hypernym
comment
En teoría de la complejidad co ...... garítmica y tamaño polinómico.
@es
En théorie de la complexité, u ...... produit matriciel est dans NC.
@fr
In complexity theory, the clas ...... NC with access to randomness.
@en
NC steht in der Informatik als ...... (siehe auch Parallelisierung).
@de
Na teoria da complexidade, a c ...... se com acesso a aleatoriedade.
@pt
Nella teoria della complessità ...... he le ha introdotte per primo.
@it
在计算复杂度理论，NC（Nick's Class），是一个复 ...... EREW都是不受影响的。 RNC是随机化方向的对NC的扩展。
@zh
計算複雑性理論において、NC（Nick's Class）とは ...... らなる一様ブール回路で解ける決定問題の集合という定義もある。
@ja
label
NC (Komplexitätsklasse)
@de
NC (clase de complejidad)
@es
NC (complessità)
@it
NC (complexidade)
@pt
NC (complexity)
@en
NC (complexité)
@fr
NC (复杂度)
@zh
NC (計算複雑性理論)
@ja