| rdfs:comment
| - NC steht in der Informatik als Abkürzung für Nick's Class (nach Nick Pippenger), die Komplexitätsklasse der parallel effizient lösbaren Entscheidungsprobleme. Die Motivation zur Bildung und Untersuchung der Klasse NC ergibt sich daraus, Probleme zu identifizieren, die auf einem Parallelrechner in deutlich besserer Zeit als auf einer sequentiell arbeitenden Maschine bei einer vertretbar großen Zahl von Prozessoren gelöst werden können. (de)
- En théorie de la complexité, un domaine de l'informatique théorique, NC (pour Nick's class) est une classe de complexité faisant intervenir le parallélisme. C'est l'ensemble des problèmes de décision décidés en temps polylogarithmique par un nombre polynomial de machines en parallèle. Elle correspond aux problèmes considérés comme facilement traitables par une architecture parallèle. La classe a été nommée par Stephen Cook en l'honneur de Nick Pippenger, qui a travaillé sur le sujet. Par exemple, le (problème de décision associé au calcul du) produit matriciel est dans NC. (fr)
- Nella teoria della complessità i problemi NC sono i problemi efficientemente parallelizzabili, ovvero risolvibili in tempo , avendo a disposizione una quantità di hardware polinomiale rispetto alla dimensione dell'input. La classe NC prende il nome dallo studioso , suo primo ideatore. (it)
- 在计算复杂度理论，NC（Nick's Class），是一个复杂度类，是能被并行计算机在多对数函数时间（O(logc n)）内以多项式空间（或者说O(nk)并行线程）下解决的判定问题的集合，最先由史提芬·古克提出。 正如P被认为是易解复杂度类一般，NC也被认为是在并行计算上易解的问题。明显的有NC ⊆ P，因为一切并行计算都可以以多项式空间依次的在确定型图灵机上运行。我们目前仍未知道的一个关键问题是，NC = P是否成立。大多数的研究人员都认为这是不可能的——否则的话这意味着一切都可以并行计算化。正如NP完全对于P来说是怀疑难解复杂度类一样，P完全对于NC来说也是“怀疑难解”的。 定义中的并行计算机,可以看作为一个并行，公共的PRAM池，所有的并行线程都可以在任意时间访问池的任意位置，NC的定义不受是否可以同时访问的影响，当然无论是，还是都是不受影响的。 是随机化方向的对NC的扩展。 (zh)
- En teoria de la complexitat, la classe de complexitat NC (la Classe d'en Nick o NIck's class) és el conjunt de problemes de decisió que es poden resoldre en un temps polilogarítmic en un computador paral·lel amb un nombre polinòmic de processadors. Dit d'una d'altra manera, un problema és a NC si existeixen unes constants c i k tals que es pot solucionar en temps O(logc n) fent servir un nombre O(nk) de processadors paral·lels. La classe va ser batejada per Stephen Cook en honor de , que havia treballat en aquesta mena de problemes. (ca)
- En teoría de la complejidad computacional, la clase de complejidad NC (la clase de Nick) es el conjunto de los problemas de decisión que pueden ser resueltos mediante computación paralela con un número polinómico de procesadores en tiempo polilogarítmico. Dicho de otra forma, un problema está en NC si existen constantes c y k tales que el problema puede ser resuelto en tiempo O((log n)c) utilizando O(nk) procesadores paralelos. Stephen Cook acuñó el término NC (Clase de Nick) en honor a , quien ha investigado los circuitos de profundidad polilogarítmica y tamaño polinómico. (es)
- In 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 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. (en)
- 계산 복잡도 이론에서 NC(Nick's Class)는 프로세서가 다항 개인 병렬 컴퓨터가 다항로그 시간에 판정할 수 있는 판정 문제의 집합이다. 다시 말해서, 어떤 문제가 NC라는 것은, 이 문제를 상수 와 에 대해서 병렬 프로세서 개를 써서 시간에 풀 수 있다는 뜻이다. 스티븐 쿡은 회로를 다항로그 깊이와 다항 크기에 대해서 연구를 많이 한 의 이름을 따서 Nick's Class 닉 클래스[*]라는 이름을 지었다. P를 결정론적 튜링 기계가 다룰 수 있는 문제들로 보는 것과 마찬가지로, NC도 병렬 컴퓨터가 효율 있게 다룰 수 있는 문제로 볼 수 있다. 병렬 컴퓨터는 순차 컴퓨터가 시뮬레이트할 수 있기 때문에 NC는 P의 부분집합이다. NC = P인지는 아직 밝혀지지 않았지만, 학계에서는 이 명제가 거짓일 것으로 보고 있다. "본래 순차"이기 때문에 병렬화해서 빠르게 할 수 없는 문제가 존재할 것이라는 뜻이다. NP-완전을 "다룰 수 없을 것 같은" 문제로 보는 것과 같다. 따라서 P-완전도 "병렬화할 수 없을 것 같은", "본래 순차일 것 같은" 문제로 생각할 수 있다. (ko)
- 計算複雑性理論において、NC（Nick's Class）とは多項式個数のプロセッサで構成される並列計算機で，問題サイズの対数について多項式時間で解ける決定問題の複雑性クラスである。換言すれば、NC に属する問題は、O(nk)個の並列プロセッサを使って O((log n)c) の時間で解ける（c と k は定数）。"Nick's Class" という用語はスティーブン・クックの造語で、計算機科学者 Nick Pippenger にちなんでいる。 クラス P と同様、NC に属する問題は並列計算機で効率的に解くことができると見なされている。並列計算機は通常の計算機でシミュレート可能であるため、NC は P に含まれる。NC = P かどうかは判っていないが、おそらく違うだろうと言われている。つまり、多項式時間で解ける問題には「本質的に逐次的」なものがあり、並列化によって高速化できないと考えられている。NP完全問題は効率的に解けないと考えられているように、P完全問題は「本質的に並列化不可能」または「本質的に逐次的」であると考えられている。 NC の別の定義として、の深さと多項式個の論理ゲートからなる一様ブール回路で解ける決定問題の集合という定義もある。 NC クラス群と L および NL の関係は Papadimitriou 1994, Theorem 16.1 により次のように示される。 (ja)
- Na teoria da complexidade, a classe NC (para "Classe de Nick") é o conjunto de Problema de decisão decidíveis em tempo polilogarítmico em um computador paralelo com um número polinomial de processadores. Em outras palavras, um problema é no NC se existem constantes c e k tal que ele pode ser resolvido no tempo O(logc n) usando O(nk) processadores paralelos. Stephen Cook deu o nome de "classe de Nick", depois de Nick Pippenger, que tinha feito uma extensa pesquisa sobre circuitos com profundidade polilogaritmica e tamanho polinomial. RNC é um NC estendendo classe com acesso a aleatoriedade. (pt)
- В теорії складності обчислень класом NC (від англ. Nick’s Class) називають множину задач розв'язності, що розв'язуються за полілогарифмічний час на паралельному комп'ютері з поліноміальним числом процесорів. Іншими словами, задача належить до класу NC, якщо існують константи і такі, що її можна розв'язати за час при використанні паралельних процесорів. Стівен Кук назвав його «класом Ніка» на честь , який широко дослідив схеми з полілогарифмічною глибиною і поліноміальним розміром. (uk)
- В теории сложности вычислений классом NC (от англ. Nick’s Class) называют множество задач разрешимости, разрешимых за полилогарифмическое время на параллельном компьютере с полиномиальным числом процессоров. Другими словами, задача принадлежит классу NC, если существуют константы и такие, что она может быть решена за время при использовании параллельных процессоров. Стивен Кук назвал его «Классом Ника» в честь , который провел обширные исследования схем с полилогарифмической глубиной и полиномиальным размером. (ru)
|
![[RDF Data]](/fct/images/sw-rdf-blue.png)
![[cxml]](/fct/images/cxml_doc.png)
![[csv]](/fct/images/csv_doc.png)
![[text]](/fct/images/ntriples_doc.png)
![[turtle]](/fct/images/n3turtle_doc.png)
![[ld+json]](/fct/images/jsonld_doc.png)
![[rdf+json]](/fct/images/json_doc.png)
![[rdf+xml]](/fct/images/xml_doc.png)
![[atom+xml]](/fct/images/atom_doc.png)
![[html]](/fct/images/html_doc.png)