NC (complexity class)

NC stands in computer science as an abbreviation for Nick's Class (after Nick Pippenger ), the complexity class of decision problems that can be solved efficiently in parallel . The motivation for creating and examining the NC class arises from identifying problems that can be solved on a parallel computer in a significantly better time than on a sequentially operating machine with a reasonably large number of processors.

definition

A parallel machine model , the so-called PRAM ( Parallel Random Access Machine ), is used to define the NC class . This is a register machine that has been expanded to include options for the parallel processing of commands, clearly with an arbitrarily large number of processors or accumulators . A problem belongs to the NC class if it can be resolved in polylogarithmic time (i.e. in , constant) and with a polynomial number of processors (i.e. , k constant) used in parallel on a PRAM. The product of computing time and the number of processors is called effort. ${\ displaystyle {\ mathcal {O}} \ left (\ log ^ {c} n \ right)}$ ${\ displaystyle c}$ ${\ displaystyle {\ mathcal {O}} \ left (n ^ {k} \ right)}$

In circuit complexity , NC is defined in terms of circuits . For everyone is the class of all languages that are recognized by a uniform circuit family with polynomial size, depth and a fan-in of at most 2. Then is . Uniform NC contains the languages recognized by LOGSPACE uniform NC families. ${\ displaystyle i \ in \ mathbb {N}}$ ${\ displaystyle {\ mbox {NC}} ^ {i}}$ ${\ displaystyle {\ mathcal {O}} \ left (\ log ^ {i} (n) \ right)}$ ${\ displaystyle {\ mbox {NC}} = \ bigcup _ {i = 0} ^ {\ infty} {\ mbox {NC}} ^ {i}}$

Explanation

In summary and simplified this means: A problem is considered to be efficiently solvable by a machine working in parallel if the problem can be solved in logarithmic time. For comparison, it should be noted that with sequentially operating machines, a problem is considered to be efficiently solvable if the problem can be solved in polynomial time.

On a sequentially operating machine with only one processor, the time complexity equals the effort complexity. Conversely, the effort on a machine working in parallel describes the time that a machine working in sequence needs for the calculation.

hierarchy

Obviously applies to all ${\ displaystyle i \ in \ mathbb {N}}$

{\ displaystyle {\ mbox {NC}} ^ {i} \ subseteq {\ mbox {NC}} ^ {i + 1}}

It is known that beyond that applies. Otherwise, it is unknown whether the inclusion is real. If you only look at monotonous circuits, the inclusion is always real. ${\ displaystyle {\ mbox {NC}} ^ {0} \ subsetneq {\ mbox {NC}} ^ {1}}$ ${\ displaystyle {\ mbox {NC}} ^ {i}}$

Relation to other complexity classes

NC and P

The relationship between NC and P is similar to that between P and NP ( see also P-NP problem ). So it definitely applies , but it is unclear whether and thus whether also applies. One generally assumes that NC is a proper subset of P, so . ${\ displaystyle {\ mbox {NC}} \ subseteq {\ mbox {P}}}$ ${\ displaystyle {\ mbox {NC}} \ supseteq {\ mbox {P}}}$ ${\ displaystyle {\ mbox {NC}} = {\ mbox {P}}}$ ${\ displaystyle {\ mbox {NC}} \ subsetneq {\ mbox {P}}}$

This also shows that the relationship between P-complete problems and problems from NC is the same as that between NP-complete problems and problems from P: If one were to find even a single P-complete problem that lies in NC, it would follow automatically . Based on the conjecture , one assumes that there is no P-complete problem in NC. ${\ displaystyle {\ mbox {NC}} = {\ mbox {P}}}$ ${\ displaystyle {\ mbox {NC}} \ neq {\ mbox {P}}}$

Other classes

It is NC = AC , moreover, applies to all : . A similar reference applies to the TC hierarchy. In the case where: . This follows from the fact that NC ^{0 can} not calculate a function that depends on all input bits, thus separating the two classes of problems that are obviously in AC ⁰ and depend on all bits, e.g. the OR function, and from the fact that Parity is not in AC ⁰ . ${\ displaystyle i \ in \ mathbb {N}}$ ${\ displaystyle {\ mbox {NC}} ^ {i} \ subseteq {\ mbox {AC}} ^ {i} \ subseteq {\ mbox {NC}} ^ {i + 1}}$ ${\ displaystyle i = 0}$ ${\ displaystyle {\ mbox {NC}} ^ {0} \ subsetneq {\ mbox {AC}} ^ {0} \ subsetneq {\ mbox {NC}} ^ {1}}$

The levels of the NC hierarchy relate to L and NL as follows :

{\ displaystyle {\ mbox {NC}} ^ {1} \ subseteq {\ mbox {L}} \ subseteq {\ mbox {NL}} \ subseteq {\ mbox {NC}} ^ {2} \ subseteq {\ mbox {NC}}}

In descriptive complexity theory , NC corresponds to class . ${\ displaystyle FO \ left [\ log (n) ^ {{\ mathcal {O}} (1)} \ right]}$

literature

Sanjeev Arora and Boaz Barak: Computational Complexity. A modern approach . Cambridge University Press, Cambridge 2009, ISBN 978-0-521-42426-4 .
Stasys Jukna: Boolean function complexity. Advances and frontiers . Springer, 2012, ISBN 978-3-642-24507-7 .
Christos H. Papadimitriou: Computational Complexity . Addison-Wesley, Reading / Mass. 1995, ISBN 0-201-53082-1 .

Web links

NC . In: Complexity Zoo. (English)

Individual evidence

↑ Definition follows https://complexityzoo.uwaterloo.ca/Complexity_Zoo:N#nc Uniformity is not always assumed.
^ Sanjeev Arora and Boaz Barak: Computational Complexity. A modern approach . Cambridge University Press, Cambridge 2009, ISBN 978-0-521-42426-4 . , Page 117
^ R. Raz and P. McKenzie: Separation of the monotone NC hierarchy . In: Combinatorica . tape 19 , no. 3 . Springer, 1999, p. 403-435 ( psu.edu [PDF]).
↑ Papadimitriou 1994, Theorem 16.1
↑ https://complexityzoo.uwaterloo.ca/Complexity_Zoo:N#nc

[1] Definition follows https://complexityzoo.uwaterloo.ca/Complexity_Zoo:N#nc Uniformity is not always assumed.

[2] Sanjeev Arora and Boaz Barak: Computational Complexity. A modern approach . Cambridge University Press, Cambridge 2009, ISBN 978-0-521-42426-4 . , Page 117

[3] R. Raz and P. McKenzie: Separation of the monotone NC hierarchy . In: Combinatorica . tape 19 , no. 3 . Springer, 1999, p. 403-435 ( psu.edu [PDF]).

[4] Papadimitriou 1994, Theorem 16.1

[5] ttps://complexityzoo.uwaterloo.ca/Complexity_Zoo:N#nc