CC (complexity)

Uses your system voice; voice and rate in settings.

Snapshot

≈ 1 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

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.

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.

References

Text derived from https://en.wikipedia.org/w/index.php?oldid=1268348595 under CC BY-SA 4.0; modifications have been made.

Provenance

snapshot enwiki-001268348595 · captured 1736409996.0 · version history

Cite this page as: encyclopegia.org, “CC (complexity)”, snapshot enwiki-001268348595. https://encyclopegia.org/a/cc-complexity

Sources cited in this revision

1 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.