| dbo:abstract
|
- 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. També es pot definir NC com el conjunt de problemes de decisió que poden ser solucionats per un circuit Booleà d'una profunditat polilogarítmica i un nombre de portes polinòmic. La classe va ser batejada per Stephen Cook en honor de , que havia treballat en aquesta mena de problemes. Es pot assumir que el computador paral·lel de la definició és un computador paral·lel PRAM, això és, que està format per un seguit de processadors que poden accedir a una memòria principal comuna en un temps constant. La definició de la classe no es veu afectada per com es gestionen els accessos simultanis a un bit per part de diferents processadors. De la mateixa manera que la classe P es pot veure com la classe dels problemes tractables, la classe NC es pot veure com els problemes que es poden tractar en ordinadors paral·lels. (ca)
- 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 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. Al igual que los problemas de P pueden verse como los problemas resolubles en una máquina secuencial, los de NC pueden verse como aquellos que pueden resolverse eficientemente en una máquina paralela. NC es subconjunto de P dado que las máquinas paralelas pueden simularse con máquinas secuenciales. No se ha determinado si NC = P, pero se piensa que son clases diferentes, lo que querría decir que algunos problemas no pueden ser mejorados usando una máquina paralela. Al igual que la clase NP-completo puede verse como la clase de problemas "seguramente sin solución eficiente", la clase P-completo puede verse como la clase de problemas "seguramente no paralelizables". 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. Just as the class P 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 is a subset of P because polylogarithmic parallel computations can be simulated by polynomial-time sequential ones. It is unknown whether NC = P, but most researchers suspect this to be false, meaning that there are probably some tractable problems that are "inherently sequential" and cannot significantly be sped up by using parallelism. Just as the class NP-complete can be thought of as "probably intractable", so the class P-complete, when using NC reductions, can be thought of as "probably not parallelizable" or "probably inherently sequential". The parallel computer in the definition can be assumed to be a parallel, random-access machine (PRAM). That is a parallel computer with a central pool of memory, and any processor can access any bit of memory in constant time. The definition of NC is not affected by the choice of how the PRAM handles simultaneous access to a single bit by more than one processor. It can be CRCW, CREW, or EREW. See PRAM for descriptions of those models. Equivalently, NC can be defined as those decision problems decidable by a uniform Boolean circuit (which can be calculated from the length of the input, for NC, we suppose we can compute the Boolean circuit of size n in logarithmic space in n) with polylogarithmic depth and a polynomial number of gates with a maximum fan-in of 2. RNC is a class extending NC with access to randomness. (en)
- 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)
- 計算複雑性理論において、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完全問題は「本質的に並列化不可能」または「本質的に逐次的」であると考えられている。 この定義における並列計算機は「並列ランダムアクセス機械」（PRAM）である。これは、共有メモリ型の並列計算機の計算モデルで、全プロセッサがどのメモリ位置についても一定の時間でアクセスできるものと定義されている。NC の定義は PRAM において複数のプロセッサが同じメモリ位置にアクセスした場合の対処方法には影響されない。この排他モデルとして CRCW、CREW、EREW がある。詳しくはPRAMを参照されたい。 NC の別の定義として、の深さと多項式個の論理ゲートからなる一様ブール回路で解ける決定問題の集合という定義もある。 NCi は、多項式個の論理ゲートからなる一様ブール回路（深さ O((log n)i)）で解ける決定問題の集合である。また、多項式個のプロセッサからなる並列計算機上で O((log n)i) 時間で解ける決定問題の集合でもある。 NC クラス群と L および NL の関係は Papadimitriou 1994, Theorem 16.1 により次のように示される。 同様に、NCi は、交替性チューリングマシンで O(log n) の領域と (log n)O(1) 回の交替で解ける決定問題の集合と同じである。 (ja)
- 계산 복잡도 이론에서 NC(Nick's Class)는 프로세서가 다항 개인 병렬 컴퓨터가 다항로그 시간에 판정할 수 있는 판정 문제의 집합이다. 다시 말해서, 어떤 문제가 NC라는 것은, 이 문제를 상수 와 에 대해서 병렬 프로세서 개를 써서 시간에 풀 수 있다는 뜻이다. 스티븐 쿡은 회로를 다항로그 깊이와 다항 크기에 대해서 연구를 많이 한 의 이름을 따서 Nick's Class 닉 클래스[*]라는 이름을 지었다. P를 결정론적 튜링 기계가 다룰 수 있는 문제들로 보는 것과 마찬가지로, NC도 병렬 컴퓨터가 효율 있게 다룰 수 있는 문제로 볼 수 있다. 병렬 컴퓨터는 순차 컴퓨터가 시뮬레이트할 수 있기 때문에 NC는 P의 부분집합이다. NC = P인지는 아직 밝혀지지 않았지만, 학계에서는 이 명제가 거짓일 것으로 보고 있다. "본래 순차"이기 때문에 병렬화해서 빠르게 할 수 없는 문제가 존재할 것이라는 뜻이다. NP-완전을 "다룰 수 없을 것 같은" 문제로 보는 것과 같다. 따라서 P-완전도 "병렬화할 수 없을 것 같은", "본래 순차일 것 같은" 문제로 생각할 수 있다. 이 정의에서 병렬 컴퓨터는 병렬이고 임의로 접근할 수 있는 기계라고 볼 수 있다. 이 기계는 메모리를 공유하는 병렬 컴퓨터로, 어떤 프로세서도 메모리에 있는 임의의 비트를 상수 시간에 접근할 수 있다. NC의 정의는 PRAM이 여러 프로세서가 동시에 한 비트에 접근하는 방법을 어떻게 제어하는지에 영향을 받지 않는다. 그 방법에는 CRCW, CREW, EREW 등이 있다. 이러한 모델에 대한 설명은 을 참고하라. 이와 동등하게 NC는 깊이에 게이트가 다항개인 가 판정할 수 있는 판정 문제들로 정의할 수 있다. 는 게이트가 다항개이고 깊이가 인 균일 불 회로로 판정할 수 있는 판정 문제의 복잡도 종류이다. 즉, 프로세서가 다항개인 병렬 컴퓨터로 시간에 풀 수 있는 판정 문제의 집합이다. NC를 공간 복잡도인 L and NL와 관련지을 수 있다. 크리스토스 파파디미트리우가 지은 《계산 복잡도》에 나오는 정리 16.1에 따르면 다음 관계가 성립한다고 한다. 이와 비슷하게, 는 교대 튜링 기계가 공간을 쓰고 만큼 교대를 해서 풀 수 있는 문제의 집합과 같다. (ko)
- 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)
- 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. Tal como a classe P pode ser pensado como os problemas tratáveis (tese de Cobham), de modo NC podem ser considerados como os problemas que podem ser eficazmente resolvidos num computador paralelo. NC é um subconjunto de P porque computações paralelas polilogaritmicas podem ser simuladas por seqüenciais de tempo polinomial. Desconhece-se se NC = P, mas a maioria dos pesquisadores suspeitam que isso é falso, o que significa que provavelmente existem alguns problemas tratáveis que são "inerentemente sequencial" e não pode ser significativamente acelerada usando paralelismo. Tal como a classe NP-Completo pode ser pensado como "provavelmente intratável", por isso a classe P-Completa, ao utilizar reduções NC, pode ser pensado como "provavelmente não paralelizável" ou "provavelmente inerentemente sequencial". O computador paralelo na definição pode ser considerado como uma máquina de acesso aleatório paralelo (PRAM). Isso é um computador paralelo com uma grupo central da memória, e qualquer processador pode acessar qualquer bit de memória em tempo constante. A definição de NC não é afetado pela escolha do modo como o PRAM manipula o acesso simultâneo a um único bit, por mais do que um processador. Pode ser CRCW, CREW, ou EREW. Veja PRAM para descrições desses modelos. Equivalentemente, NC podem ser definidos como aqueles problemas de decisão decidíveis por um circuito booleano uniforme (o que pode ser calculado a partir do comprimento da entrada) com profundidade polilogaritmicas e um número polinomial de portas. RNC é um NC estendendo classe com acesso a aleatoriedade. (pt)
- 在计算复杂度理论，NC（Nick's Class），是一个复杂度类，是能被并行计算机在多对数函数时间（O(logc n)）内以多项式空间（或者说O(nk)并行线程）下解决的判定问题的集合，最先由史提芬·古克提出。 正如P被认为是易解复杂度类一般，NC也被认为是在并行计算上易解的问题。明显的有NC ⊆ P，因为一切并行计算都可以以多项式空间依次的在确定型图灵机上运行。我们目前仍未知道的一个关键问题是，NC = P是否成立。大多数的研究人员都认为这是不可能的——否则的话这意味着一切都可以并行计算化。正如NP完全对于P来说是怀疑难解复杂度类一样，P完全对于NC来说也是“怀疑难解”的。 定义中的并行计算机,可以看作为一个并行，公共的PRAM池，所有的并行线程都可以在任意时间访问池的任意位置，NC的定义不受是否可以同时访问的影响，当然无论是，还是都是不受影响的。 是随机化方向的对NC的扩展。 (zh)
- В теорії складності обчислень класом NC (від англ. Nick’s Class) називають множину задач розв'язності, що розв'язуються за полілогарифмічний час на паралельному комп'ютері з поліноміальним числом процесорів. Іншими словами, задача належить до класу NC, якщо існують константи і такі, що її можна розв'язати за час при використанні паралельних процесорів. Стівен Кук назвав його «класом Ніка» на честь , який широко дослідив схеми з полілогарифмічною глибиною і поліноміальним розміром. Так само, як клас P можна вважати класом податливих задач, так і NC можна вважати класом задач, які можна ефективно розв'язати на паралельному комп'ютері. NC — це підмножина P, тому що паралельні полілогарифмічні обчислення можна симулювати за допомогою послідовних поліноміальних обчислень. Невідомо, чи NP = P, але більшість учених вважає, що ні, з чого випливає, що найпевніше існують податливі задачі, які послідовні «від природи», і не можуть бути істотно прискореними за використання паралелізму. Так само, як клас NP-повних задач можна вважати класом «найпевніше непіддатливих» задач, так і клас , при зведенні до NC, можна вважати «найпевніше непаралелізовним» або «найпевніше послідовним від природи». Паралельний комп'ютер у визначенні можна вважати паралельною машиною з довільним доступом (PRAM — від англ. parallel, random-access machine). Це паралельний комп'ютер із центральним пулом пам'яті, будь-який процесор якого може отримати доступ до будь-якого біта за сталий час. На визначення NC не впливає спосіб, за допомогою якого PRAM здійснює одночасний доступ декількох процесорів до одного біта. NC можна визначити, як множину задач розв'язності, розв'язуваних з полілогарифмічною глибиною і поліноміальним числом вентилів. (uk)
- В теории сложности вычислений классом NC (от англ. Nick’s Class) называют множество задач разрешимости, разрешимых за полилогарифмическое время на параллельном компьютере с полиномиальным числом процессоров. Другими словами, задача принадлежит классу NC, если существуют константы и такие, что она может быть решена за время при использовании параллельных процессоров. Стивен Кук назвал его «Классом Ника» в честь , который провел обширные исследования схем с полилогарифмической глубиной и полиномиальным размером. Так же, как класс P можно считать классом податливых задач, так и NC можно считать классом задач, которые могут быть эффективно решены на параллельном компьютере. NC — это подмножество P, потому что параллельные полилогарифмические вычисления можно симулировать с помощью последовательных полиномиальных вычислений. Неизвестно, верно ли NP = P, но большинство ученых считает, что нет, из чего следует, что скорее всего существуют податливые задачи, которые последовательны «от природы», и не могут быть существенно ускорены при использовании параллелизма. Так же, как класс NP-полных задач можно считать классом «скорее всего неподатливых» задач, так и класс P-полных задач, при сведении к NC, можно считать «скорее всего не параллелизуемым» или «скорее всего последовательным от природы». Параллельный компьютер в определении можно считать параллельной машиной с произвольным доступом (PRAM — от англ. parallel, random-access machine). Это параллельный компьютер с центральным пулом памяти, любой процессор которого может получить доступ к любому биту за константное время. На определение NC не влияет способ, с помощью которого PRAM осуществляет одновременный доступ нескольких процессоров к одному биту. NC может быть определён, как множество задач разрешимости, разрешимых распределённой Булевой схемой с полилогарифмической глубиной и полиномиальным числом вентилей. (ru)
|
| 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)
|
