NC (complexity)¶

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.

Version: v1 · 2026-09-28 · History
Domain-specific #: 10927
Domain group: Applied Sciences & Engineering
Origin domain: Computer Science & Software Engineering
Subdomain: Computational Complexity Theory → Computer Science & Software Engineering

Core Idea¶

NC (complexity) is treated here as the recurring mathematics and formal science identity summarized by this source-grounded definition: 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 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.

Scope of Application¶

Problems in NC. As with P, by a slight abuse of language, one might classify function problems and search problems as being in NC.
The NC hierarchy. The smallest class, NC 0 , is the class of functions definable by Boolean circuits with constant depth and bounded fan-in.
Barrington's theorem. Each of the instructions is a tuple (i, p, q) where i is the index of variable to check (1 ≤ i ≤ n), and p and q are functions from {1, 2, ...
Barrington's theorem. The function mapping an input to a final state of the program is called the yield of the program (more precisely, the yield on an input is the function mapping any.
Barrington's theorem. The program accepts a set A \subseteq 2^n of variable values when there is some set of functions F \subseteq k^k such that a variable sequence x \in.

Clarity¶

A clear use of NC (complexity) names the carrier, the operative relation, and the conditions under which the source treats the identity as present. The minimal definition is 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.

Manages Complexity¶

NC (complexity) compresses multiple mathematics and formal science details into a stable diagnostic relation. The source shows both the central mechanism—recursively applying such property, it is possible to build a binary tree of length O(\log(n)) in which every sum between two bits xi and xj is expressible by means of basic logical operators, e.g. through the Boolean expression (xi \land \neg xj) \lor (\neg xi \land.

Abstract Reasoning¶

Type the carrier. Identify the mathematics and formal science entities to which the claim applies.
State the relation. Use the source-grounded identity: 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.
Check operation and conditions. NC i is the class of decision problems decidable by uniform Boolean circuits with a polynomial number of gates of at most two inputs and depth , or the class.

Knowledge Transfer¶

Within the home domain. Knowledge about NC (complexity) transfers literally when a new case preserves the same carrier type, relation, and recognition test. As with P, by a slight abuse of language, one might classify function problems and search problems as being in NC. The smallest class, NC 0 , is the class of functions definable by Boolean circuits with constant depth and bounded fan-in. Beyond the home domain. No canonical parent is asserted for NC (complexity).

Relationships to Other Abstractions¶

Current abstraction NC (complexity) Domain-specific

Parents (1) — more general patterns this builds on

NC (complexity) is a kind of Complexity Class Domain-specific

NC (complexity) is a domain-specific kind of complexity class under the frozen identity and differentia. Complete-catalog comparison found the corresponding live broader identity.

Neighborhood in Abstraction Space¶

NC (complexity) sits in a crowded region of the domain-specific corpus (35^th percentile for distinctiveness): several abstractions share nearly its structure, so a description that fits it tends to fit its neighbors too.

Family — Computation Models & Complexity Classes (37 abstractions)

Nearest neighbors

Computed from structural-signature embeddings · 2026-10-08