CC (complexity) (original) (raw)
En teoria de la complexitat, la classe de complexitat CC (circuits comparadors, comparator circuits) és el conjunt dels problemes de decisió que poden ser resolts amb de mida polinòmica. Un circuit comparador és una xarxa de fils i portes. Cada porta comparador, que és una aresta dirigida connectant dos fils, agafa dues entrades i les treu en ordre. Cada entrada pot ser una variable, la seva negada o una constant. Un els fils s'etiqueta com el fil de sortida. També es pot definir la classe CC com la dels problemes en espai logarítmic reduïbles a la classe CCVP.
| Property | Value |
|---|---|
| dbo:abstract | En teoria de la complexitat, la classe de complexitat CC (circuits comparadors, comparator circuits) és el conjunt dels problemes de decisió que poden ser resolts amb de mida polinòmica. Un circuit comparador és una xarxa de fils i portes. Cada porta comparador, que és una aresta dirigida connectant dos fils, agafa dues entrades i les treu en ordre. Cada entrada pot ser una variable, la seva negada o una constant. Un els fils s'etiqueta com el fil de sortida. També es pot definir la classe CC com la dels problemes en espai logarítmic reduïbles a la classe CCVP. (ca) 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. (en) Na teoria da complexidade computacional, CC (circuito comparador) é a classe de complexidade que contém problemas de decisão que podem ser resolvidos por circuitos comparadores de tamanho polinomial. Circuitos comparadores são redes em que cada um dos pórticos de comparação é direcionado, cada fio é inicializado com uma variável de entrada, a sua negação, ou uma constante, e um dos fios é distinguido como o fio de saída. O problema mais importante, que é completa para CC é uma variante decisão do problema da união estável. (pt) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Comparator_gate_in_a_comparator_circuit.png?width=300 |
| dbo:wikiPageID | 37764147 (xsd:integer) |
| dbo:wikiPageLength | 6044 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1082271575 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Scott_Aaronson dbr:Decision_problem dbr:NC_(complexity) dbr:NL_(complexity) dbr:L_(complexity) dbr:Complexity_class dbr:Computational_complexity_theory dbr:P_(complexity) dbr:Digi-Comp_II dbr:Unary_numeral_system dbc:Complexity_classes dbr:AC0 dbc:Circuit_complexity dbr:Bipartite_graph dbr:Polynomial dbr:Sorting_network dbr:Stable_marriage_problem dbr:File:Comparator_gate_in_a_comparator_circuit.png dbr:File:BitonicSort1.svg |
| dbp:wikiPageUsesTemplate | dbt:Reflist dbt:ComplexityClasses dbt:CZoo |
| dct:subject | dbc:Complexity_classes dbc:Circuit_complexity |
| gold:hypernym | dbr:Class |
| rdf:type | yago:WikicatComplexityClasses yago:Abstraction100002137 yago:Class107997703 yago:Collection107951464 yago:Group100031264 |
| rdfs:comment | En teoria de la complexitat, la classe de complexitat CC (circuits comparadors, comparator circuits) és el conjunt dels problemes de decisió que poden ser resolts amb de mida polinòmica. Un circuit comparador és una xarxa de fils i portes. Cada porta comparador, que és una aresta dirigida connectant dos fils, agafa dues entrades i les treu en ordre. Cada entrada pot ser una variable, la seva negada o una constant. Un els fils s'etiqueta com el fil de sortida. També es pot definir la classe CC com la dels problemes en espai logarítmic reduïbles a la classe CCVP. (ca) 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. (en) Na teoria da complexidade computacional, CC (circuito comparador) é a classe de complexidade que contém problemas de decisão que podem ser resolvidos por circuitos comparadores de tamanho polinomial. Circuitos comparadores são redes em que cada um dos pórticos de comparação é direcionado, cada fio é inicializado com uma variável de entrada, a sua negação, ou uma constante, e um dos fios é distinguido como o fio de saída. O problema mais importante, que é completa para CC é uma variante decisão do problema da união estável. (pt) |
| rdfs:label | CC (Complexitat) (ca) CC (complexity) (en) Circuito comparador (pt) |
| owl:sameAs | freebase:CC (complexity) yago-res:CC (complexity) wikidata:CC (complexity) dbpedia-ca:CC (complexity) dbpedia-pt:CC (complexity) https://global.dbpedia.org/id/4eAQV |
| prov:wasDerivedFrom | wikipedia-en:CC_(complexity)?oldid=1082271575&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/BitonicSort1.svg wiki-commons:Special:FilePath/Comparator_gate_in_a_comparator_circuit.png |
| foaf:isPrimaryTopicOf | wikipedia-en:CC_(complexity) |
| is dbo:wikiPageDisambiguates of | dbr:CC |
| is dbo:wikiPageWikiLink of | dbr:CC dbr:Digi-Comp_II |
| is foaf:primaryTopic of | wikipedia-en:CC_(complexity) |
