CC (complexity)
id:
cc-complexity-309-8373305
title:
CC (complexity)
text:
In computational complexity theory, CC 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.
brand slug:
wiki
category slug:
encyclopedia
description:
original url:
https://en.wikipedia.org/wiki/CC_(complexity)
date created:
date modified:
2023-01-05T12:35:51Z
main entity:
{"identifier":"Q5009755","url":"https://www.wikidata.org/entity/Q5009755"}
image:
fields total:
13
integrity:
13