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.

Definition

A single comparator gate.

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.^[1] An equivalent definition^[2] 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.

CC-complete problems

A problem in CC is CC-complete if every problem in CC can be reduced to it using a logspace reduction. The comparator circuit value problem (CCVP) is CC-complete.

In the stable marriage problem, there is an equal number of men and women. Each person ranks all members of the opposite sex. A matching between men and women is stable if there are no unpaired man and woman who prefer each other over their current partners. A stable matching always exists. Among the stable matchings, there is one in which each woman gets the best man that she ever gets in any stable matching; this is known as the woman-optimal stable matching. The decision version of the stable matching problem is, given the rankings of all men and women, whether a given man and a given woman are matched in the woman-optimal stable matching. Although the classical Gale–Shapley algorithm cannot be implemented as a comparator circuit, Subramanian^[3] came up with a different algorithm showing that the problem is in CC. The problem is also CC-complete.

Another problem which is CC-complete is lexicographically-first maximal matching.^[3] In this problem, we are given a bipartite graph with an order on the vertices, and an edge. The lexicographically-first maximal matching is obtained by successively matching vertices from the first bipartition to the minimal available vertices from the second bipartition. The problem asks whether the given edge belongs to this matching.

Scott Aaronson showed that the pebbles model is CC-complete.^[4] In this problem, we are given a starting number of pebbles (encoded in unary) and a description of a program which may contain only two types of instructions: combine two piles of sizes $y$ and $z$ to get a new pile of size $y+z$, or split a pile of size $y$ into piles of size $\lceil y/2 \rceil$ and $\lfloor y/2 \rfloor$. The problem is to decide whether any pebbles are present in a particular pile after executing the program. He used this to show that the problem of deciding whether any balls reach a designated sink vertex in a Digi-Comp II-like device is also CC-complete.

Containments

The comparator circuit evaluation problem can be solved in polynomial time, and so CC is contained in P. On the other hand, comparator circuits can solve directed reachability,^[3] and so CC contains NL. There is a relativized world in which CC and NC are incomparable,^[2] and so both containments are strict.

References

1. E. W. Mayr, A. Subramanian (1992). "The complexity of circuit value and network stability". Journal of Computer and System Sciences 44 (2): 302–323. doi:10.1016/0022-0000(92)90024-d.
2. S. A. Cook, Y. Filmus, D. T. M. Le (2012). "The complexity of the comparator circuit value problem". arXiv:1208.2721.
3. A. Subramanian (1994). "A new approach to stable matching problems". SIAM Journal on Computing 23 (4): 671–700. doi:10.1137/s0097539789169483.
4. Aaronson, Scott (4 July 2014). "The Power of the Digi-Comp II". Shtetl-Optimized. Retrieved 28 July 2014.

External links

• Complexity Zoo: CC