NC (complexity)

NC is in the computer science as an abbreviation for Nick 's Class (after Nick Pippenger ), the complexity class of parallel efficiently solvable decision problems. The motivation for the formation and study of the class NC arises from the fact, to identify problems that can be solved on a parallel computer in much better time than on a sequentially working machine at a reasonably large number of processors ( see also parallelization ).

Definition

To define the class NC a parallel machine model is used, the so-called PRAM (Parallel Random Access Machine). It is a register machine, which has been extended to opportunities for parallel processing of commands clearly to an arbitrarily large number of processors or accumulators. A problem belongs to the class NC if it polylogarithmischer in time (that is, in O ( n log C ), c constant) and with polynomially many (ie, k constant) used in parallel processors can be decided on a PRAM. As an effort to denotes the product of the computation time and the number of processors.

In the circuit complexity of NC is defined using circuits. For all the class of all languages ​​that are of a uniform circuit family of polynomial size, depth and detected a fan-in of more than 2 was. Then is. Uniform NC contains the languages ​​that are recognized by LOGSPACE - uniform NC families.

Explanation

To summarize and simplify, this means: One considers a problem then as solved efficiently by a parallel motion machine when the problem solution can be done in logarithmic time. For comparison it should be noted that in sequential machines working a problem then considered as solved efficiently when the problem solution can be done in polynomial time.

On a sequentially operating the machine with only one processor, the time complexity is equal to the cost of complexity. Conversely, the following expenses on a parallel machine working just the time it takes for a sequentially operated machine for calculation.

Hierarchy

For all we obviously

It is known that, in addition applies. Otherwise, however, it is unknown whether the inclusion is strict. If we consider only monotone NCi circuits that inclusion is always genuine.

Relation to other complexity classes

NC and P

The ratio between the NC and P is similar to that between P and NP (see P- NP problem ). It is certainly the case NC ⊆ P, but it is unclear whether P ⊆ NC and thus whether NC = P applies. It is generally assumed that NC is a proper subset of P, ie NC ⊂ P.

This results in the same way that the relationship between P- complete problems and problems from NC is equal to that between NP- complete problems and problems in P: If you were to find even a single P -complete problem, which is located in NC, so it followed automatically NC = P. Because of the assumption P ≠ NC one therefore assumes that there are no P -complete problem in NC.

Other classes

• It is NC = AC, moreover, applies to all. An analogous relation is valid for TC hierarchy. In the case applies. This follows from this that NC0 can not calculate a function that depends on all input bits, so that the two classes of problems are separated, which are manifestly in AC0 and depend on all bits, such as the OR function, and the fact that parity is not is in AC0.
• The levels of the NC hierarchy behave as follows to L and NL:

• In the descriptive complexity theory NC corresponds to the class.