In computational complexity theory, the class NC (named "Nick's Class") includes decision problems that can be solved quickly on a parallel computer with many processors. Specifically, a problem is in NC if there are constants c and k such that it can be solved in time proportional to (log n)^c using a number of processors proportional to n^k. The name "Nick's Class" was created by Stephen Cook to honor Nick Pippenger, who studied circuits with limited depth and size. Like in circuit complexity theory, the class NC usually requires that the circuits used are uniform, meaning they follow a consistent rule for different input sizes.

Similar to the class P, which includes problems that can be solved efficiently on a regular computer, NC includes problems that can be solved efficiently using parallel computing. NC is a subset of P because tasks that use many processors in parallel can be simulated by a single processor working sequentially over a longer time. It is not known if NC equals P, but most experts believe they are different, suggesting some problems are inherently sequential and cannot be significantly sped up with parallelism. Like NP-complete problems, which are likely difficult to solve, P-complete problems (using NC reductions) are likely difficult to solve in parallel and may require sequential methods.

The parallel computer described in NC's definition is often a PRAM (parallel, random-access machine), which has a shared memory pool that all processors can access instantly. The way the PRAM handles multiple processors accessing the same memory bit at once (CRCW, CREW, or EREW models) does not change the definition of NC.

Alternatively, NC can be defined as decision problems that can be solved using a uniform Boolean circuit with limited depth, a manageable number of gates, and a maximum of two inputs per gate. The circuit's size depends on the input length and can be created using logarithmic space.

RNC is a class that includes NC but also allows the use of randomness in solving problems.

Problems in NC

NC is a group that includes certain types of problems, such as function problems and search problems. Many problems are known to be in NC, including:

• Adding, multiplying, and dividing integers;
• Multiplying matrices, finding determinants, inverses, and ranks;
• Calculating the greatest common divisor (GCD) of polynomials using methods linked to linear algebra;
• Finding a maximal matching in a set of items.

Algorithms for these problems often require unique designs and cannot always be directly copied from common methods like Gaussian elimination or the Euclidean algorithm, which rely on step-by-step operations. For example, a ripple carry adder processes information sequentially, while a carry-lookahead adder uses a different approach to speed up calculations.

An example of an NC problem is checking the parity of a bit string. This involves counting how many 1s are in a string of 0s and 1s. A simple method is to add all the bits together. Since addition can be broken into smaller parts, the total can be calculated by splitting the string into halves, then combining the results. This process can be repeated until the total is found. Using this method, the problem can be represented as a binary tree with a number of steps that grows slowly as the string length increases. Each step combines two bits using basic logical operations, such as AND and OR, to determine if they are different.

The NC hierarchy

NC is a group of decision problems that can be solved by uniform Boolean circuits with a limited number of gates, each having at most two inputs, and a depth of O(log n). These problems can also be solved in O(log n) time on a parallel computer with a polynomial number of processors. This forms the NC hierarchy.

The smallest class, NC, includes problems that can be solved using Boolean circuits with constant depth and limited fan-in. The next level, NC, is equal to BW4, which includes problems solvable by polynomial-size circuits with width 4 or less. This applies to both uniform and nonuniform cases, with DLOGTIME-uniformity being sufficient.

NC classes are connected to other complexity classes like L, SL, NL, LOGCFL, and AC. The AC classes are similar to NC but allow gates with unlimited fan-in. For each level i, NC and AC are related, and it follows that NC equals AC.

Additionally, NC is equivalent to problems solvable by an alternating Turing machine with two choices at each step, using O(log n) space and (log n)^O(1) alternations. A major open question is whether TC0 is a subset of NC1. A partial result suggests that if a problem in NC1 requires many gates in TC0, it might require superpolynomial gates, placing it outside TC0.

Uniformity conditions define how circuit families are generated. A uniform family means a Turing machine can produce circuit schematics under specific resource constraints. Different constraints may lead to different complexity classes, with stricter constraints resulting in smaller classes.

Common uniformity levels for NC include:
– NC itself, also called U_E*-uniformity, equivalent to ALOGTIME.
– LOGSPACE.
– P.
– Computable, allowing any halting Turing machine.
– Non-uniform, the strongest case, where circuits may not be generated by an algorithm.

By default, LOGSPACE uniformity is used. Researchers sometimes use NC-uniformity, defined by an ALOGTIME alternating Turing machine that halts in O(log n) time when reading a circuit description. For higher NC classes, similar uniformities apply. For k ≥ 2, NC-uniform and LOGSPACE-uniform NC are equal, both defined by alternating Turing machines that halt in O((log n)^k) time and O(log n) space.

A major open question is whether all containments in the NC hierarchy are strict. If NC equals NC for some i, then NC equals NC for all j ≥ i, causing the hierarchy to "collapse" to level i. Two possibilities exist:
1. NC1 is strictly contained within higher levels of the hierarchy.
2. Some levels of the hierarchy are equal.

It is widely believed the first possibility is true, though no proof exists. If a problem is NC-complete under LOGSPACE or NC reductions, the NC hierarchy would collapse.

Barrington's theorem

A branching program with n variables, width k, and length m is a sequence of m instructions. Each instruction is a group (i, p, q), where i is the number of the variable being checked (1 ≤ i ≤ n), and p and q are rules that change the program's state. The numbers 1 through k represent the program's states. The program starts in state 1, and each instruction (i, p, q) changes the state from x to p(x) if the i-th variable is 0, or to q(x) if the i-th variable is 1. The program's yield is the rule that maps an input to its final state. A program accepts a set A (a collection of variable combinations) when there exists a group of rules F such that an input x is in A if and only if its yield is in F.

A family of branching programs includes a branching program for every number of variables n. A family accepts a language when the program for n variables accepts the language's inputs of length n.

It is simple to show that any language L over {0,1} can be recognized by a family of branching programs with width 5 and exponential length, or by a family with exponential width and linear length.

Every regular language over {0,1} can be recognized by a family of branching programs with a fixed width and a number of instructions that grows linearly with the number of variables (since a deterministic finite automaton can be converted into a branching program). BWBP refers to the class of languages recognized by families of branching programs with limited width and polynomial length.

Barrington's theorem states that BWBP is exactly nonuniform NC. The proof relies on the fact that the symmetric group S₅ cannot be solved.

This result is surprising. For example, it shows that the majority function can be computed by a family of branching programs with constant width and polynomial size, even though one might expect a linear number of states to achieve this.

A branching program of constant width and polynomial size can be converted into a circuit in NC using divide-and-conquer methods.

Conversely, if a circuit in NC is given, assume it uses only AND and NOT gates.

Lemma 1: If a branching program sometimes acts as a permutation P and sometimes as a permutation Q, by multiplying permutations in the first instruction by α and in the last instruction by β, the program can be adjusted to behave as βPα or βQα, respectively.

A branching program α-computes a circuit C if it acts as the identity when C's output is 0 and as α when C's output is 1.

Because all 5-cycles are conjugate, if a branching program α-computes a circuit C, there exists a branching program β-computing the same circuit C with the same length, for any two 5-cycles α and β.

Lemma 2: There exist 5-cycles γ and δ such that their commutator ε = γδγ⁻¹δ⁻¹ is also a 5-cycle. For example, γ = (1 2 3 4 5), δ = (1 3 5 4 2), and ε = (1 3 2 5 4).

Barrington's theorem is proven by induction. Suppose a circuit C takes inputs x₁, …, xₙ, and assume that for all subcircuits D of C and 5-cycles α, there exists a branching program α-computing D. Then, for all 5-cycles α, there exists a branching program α-computing C.

By assuming subcircuits have branching programs that α-compute for all α ∈ S₅, the circuit C also has this property. The branching program's size is at most 4 times the circuit's depth. If the circuit has logarithmic depth, the branching program has polynomial length.