  Subramanian defined the complexity class CC as the set of problems log-space
reducible to the comparator circuit value problem. He proved that several other
problems are complete for CC, including the stable marriage problem, and
finding the lexicographical first maximal matching in a bipartite graph. We
suggest alternative definitions of CC based on different reducibilities and
introduce a two-sorted theory VCC* based on one of them. We sharpen and
simplify Subramanian's completeness proofs for the above two problems and
formalize them in VCC*.
