Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
CC (complexity)
open-in-new
<p>In <a href="/facts/Computational_complexity_theory/etHuVF3U">computational complexity theory</a>, CC (Comparator Circuits) is the <a href="/facts/Complexity_class/IIKrcTbP">complexity class</a> containing <a href="/facts/Decision_problem/cQNWjbdE">decision problems</a> which can be solved by comparator <a href="/facts/Circuit_(computer_science)/vWgfC29C">circuits</a> of <a href="/facts/Polynomial/Lzak8VVx">polynomial</a> size. </p><p>Comparator circuits are <a href="/facts/Sorting_network/ceMfQqSh">sorting networks</a> 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. </p><p>The most important problem which is complete for CC is a decision variant of the <a href="/facts/Stable_marriage_problem/tzNRpF1f">stable marriage problem</a>. </p>