Complexity Classes and Theories for the Comparator Circuit Value Problem

Stephen A. Cook, Dai Tri Man Le, Yuli Ye

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 f…