Comparator-circuit complexity class CC¶
The class of decision problems reducible to comparator-circuit value, equivalently computable by uniform polynomial-size comparator-circuit families under the stated input conventions.
Core Idea¶
CC is the set of Boolean decision problems reducible in logarithmic space to comparator circuit value (CCV). A comparator gate sorts two bits, sending their minimum to one wire and maximum to the other. A CCV instance supplies a circuit, input values, and a designated output wire, then asks whether that output is 1. Cook, Filmus, and Lê prove equivalent descriptions of CC using weaker reductions and uniform polynomial-size comparator-circuit families under precise input-copy and negation conventions. The class is the set of qualifying problems, not one circuit or CCV alone.[ref-85108ddecc24][ref-2e953a91c975]
Use Within the Domain¶
CC identifies a common computational power across unlike problem settings. The question whether a designated edge appears in the lexicographically first maximal matching of an ordered bipartite graph is CC-complete. So is the question whether a designated man–woman pair appears in a man-optimal or woman-optimal stable marriage. These are specific yes/no versions; an unspecified task to output an entire matching is a related search problem rather than literally a member of the class of decision languages.[^ref-85108ddecc24]
The established broad containment is NL ⊆ CC ⊆ P. Whether ordinary CC and NC are incomparable is unresolved. An oracle-based separation in the original paper does not prove the corresponding unrelativized statement.[^ref-85108ddecc24]
Clarity¶
Three levels must be kept apart: a comparator gate is a local operation, CCV is a decision problem about a supplied circuit, and CC is a class of decision languages defined through reductions to that problem. Thus a matching problem can be CC-complete without itself being a physical comparator circuit. A verbal resemblance to comparison is no membership proof; the specified reduction or uniform circuit construction is needed.[^ref-85108ddecc24]
The historical notation also matters. Lê, Cook, and Ye in 2011 distinguished AC⁰-defined CC, logspace-defined CCSubr, and an oracle-based CC* without claiming their equality. The later Cook–Filmus–Lê Theorem 10 proves the relevant characterizations equivalent. Reading the older notation as three classes known today to differ reverses that chronology.[ref-2e953a91c975][ref-85108ddecc24]
Manages Complexity¶
CCV supplies a reusable complete anchor. To establish that a new decision problem belongs to CC, give an allowed answer-preserving reduction to CCV or use the equivalent uniform circuit characterization. To establish hardness, reduce a known CC-complete problem to the new problem. Once both directions are proved, later results can reuse the completeness statement instead of rebuilding the circuit simulation for each application. Membership in P alone does not establish membership in CC.[^ref-85108ddecc24]
Abstract Reasoning¶
Start by specifying the encoded input and exact Boolean question. Check the permitted comparator-gate model, uniformity and input conventions, and direction of each reduction. A reduction from the proposed problem to CCV establishes an upper bound; a reduction from CCV or another complete problem toward the proposed problem establishes hardness. The two directions answer different questions and should not be swapped.[^ref-85108ddecc24]
The named class is a strict instance of Set and Membership: each decision language is an identifiable potential member, the CCV-reduction condition is its membership rule, and CC itself is a first-class mathematical collection. The specialized comparator-circuit rule keeps this entry domain-specific. Its mathematically closer catalog neighbor Complexity Class currently has strict ancestor links that did not pass the all-instance review for CC, so that additional edge remains deferred.
Knowledge Transfer¶
The reduction method transfers from circuit evaluation to ordered graph matching and preference-based stable matching while preserving the formal yes/no question. Their input objects and proof gadgets differ; the same class-membership rule connects them. Outside formal computation, a loose analogy about “comparison” does not carry Boolean comparator gates, uniform circuit families, or reductions, and therefore does not by itself carry CC.[^ref-85108ddecc24]
Example¶
Consider an ordered bipartite graph with first-side vertices v₀, v₁, second-side vertices w₀, w₁, and edges v₀w₀, v₀w₁, v₁w₀. Greedily visit the first side in order and match each vertex to its least available neighbor. The resulting matching contains v₀w₀, leaving v₁ unmatched, so the designated-edge question answers yes for v₀w₀ and no for v₁w₀. This tiny constructed case explains the question; the paper's two-way reductions, summarized in Corollary 34, establish CC-completeness.[^ref-85108ddecc24]
Mapped back: the designated edge supplies the Boolean decision; comparator-gate constructions connect it to CCV; uniform polynomial circuit families give an equivalent computational route; and reductions in both directions support completeness. This result concerns the specified lexicographically first maximal matching decision, not arbitrary maximum matching.[^ref-85108ddecc24]
Relationships to Other Abstractions¶
Current abstraction Comparator-circuit complexity class CC Domain-specific
Parents (1) — more general patterns this builds on
-
Comparator-circuit complexity class CC is a kind of Set and Membership Prime
CC is a set of decision languages with a precise comparator-circuit membership criterion.
Hierarchy path (1) — routes to 1 parentless root
- Comparator-circuit complexity class CC → Set and Membership
Neighborhood in Abstraction Space¶
Comparator-circuit complexity class CC sits in a moderately populated region (57th percentile for distinctiveness): it has near-neighbors but no dense thicket of look-alikes.
Family — Codes, Matrices & Combinatorial Problems (32 abstractions)
Nearest neighbors
- Circuit Satisfiability — 0.87
- Boolean circuit — 0.87
- PPP (complexity) — 0.86
- NC (complexity) — 0.85
- Deferred Measurement Principle — 0.84
Computed from structural-signature embeddings · 2026-10-17
Not to Be Confused With¶
- CCV or one comparator circuit: CCV is the defining complete problem, while CC is the set of languages meeting its membership rule.[^ref-85108ddecc24]
- NC: it imposes a different computational condition, and the ordinary CC–NC relationship is unresolved.[^ref-85108ddecc24]
- SC: it requires one deterministic algorithm meeting both a polynomial-time and polylogarithmic-space bound; that condition has not been established for every CC language.[^ref-85108ddecc24]
- An unspecified stable-marriage search task: the complete examples here are designated-pair Decision variants.[^ref-85108ddecc24]
- Classification as an act: CC is the resulting mathematical set, not the live Prime's deliberate process of assigning items to categories.
- General P: CC ⊆ P does not establish P ⊆ CC.[^ref-85108ddecc24]
References¶
[^ref-85108ddecc24]: Cook, Stephen A., Yuval Filmus, and Dai Tri Man Lê. “The Complexity of the Comparator Circuit Value Problem”. arXiv:1208.2721v3, revised July 2013. https://doi.org/10.48550/arXiv.1208.2721. Full original HTML inspected, especially §§1–2.4, Theorem 10, §5 and Corollary 34, §6 and Theorems 35/50 and Corollary 51, and Appendix B. The paper's ordinary CC–NC incomparability is conjectural; the proved separation is relativized. [^ref-2e953a91c975]: Lê, Dai Tri Man, Stephen A. Cook, and Yuli Ye. “A Formal Theory for the Complexity Class Associated with the Stable Marriage Problem”. Leibniz International Proceedings in Informatics 12 (CSL 2011), 381–395. https://doi.org/10.4230/LIPIcs.CSL.2011.381. Full publisher PDF inspected. Printed pp.381–382 distinguish CC, CCSubr, and CC* and describe the matching results. Their equivalence was not claimed there; the 2013 theorem supplies it.