CC (complexity)

In computational complexity theory, CC (Comparator Circuits) is the complexity class containing decision problems which can be solved by comparator circuits of polynomial size.

Comparator circuits are sorting networks in which each comparator gate is directed, each wire is initialized with an input variable, its negation, or a constant, and one of the wires is distinguished as the output wire.

The most important problem which is complete for CC is a decision variant of the stable marriage problem.

A comparator circuit is a network of wires and gates. Each comparator gate, which is a directed edge connecting two wires, takes its two inputs and outputs them in sorted order (the larger value ending up in the wire the edge is pointing to). The input to any wire can be either a variable, its negation, or a constant. One of the wires is designated as the output wire. The function computed by the circuit is evaluated by initializing the wires according to the input variables, executing the comparator gates in order, and outputting the value carried by the output wire.

The comparator circuit value problem (CCVP) is the problem of evaluating a comparator circuit given an encoding of the circuit and the input to the circuit. The complexity class CC is defined as the class of problems logspace reducible to CCVP. An equivalent definition is the class of problems AC⁰ reducible to CCVP.

As an example, a sorting network can be used to compute majority by designating the middle wire as an output wire:

If the middle wire is designated as output, and the wires are annotated with 16 different input variables, then the resulting comparator circuit computes majority. Since there are sorting networks which can be constructed in AC⁰, this shows that the majority function is in CC.

...
Wikipedia