TC (complexity) (original) (raw)
In der Komplexitätstheorie, speziell der , ist TC eine Komplexitätsklasse und TCi eine Hierarchie von Komplexitätsklassen. Für jedes enthält TCi die formalen Sprachen, die von Schaltkreisfamilien mit Tiefe , polynomieller Größe, und Und-, Oder-, und mit unbeschränktem Fan-In erkannt werden. Die Definition erweitert damit die Klassen ACi, die keine Majority-Gatter erlaubt. Die Klasse TC ist dann definiert als Ein Majority-Gatter ist dabei ein Gatter, das genau dann 1 ausgibt, wenn mehr als die Hälfte der Eingänge den Wert 1 haben.
| Property | Value |
|---|---|
| dbo:abstract | In der Komplexitätstheorie, speziell der , ist TC eine Komplexitätsklasse und TCi eine Hierarchie von Komplexitätsklassen. Für jedes enthält TCi die formalen Sprachen, die von Schaltkreisfamilien mit Tiefe , polynomieller Größe, und Und-, Oder-, und mit unbeschränktem Fan-In erkannt werden. Die Definition erweitert damit die Klassen ACi, die keine Majority-Gatter erlaubt. Die Klasse TC ist dann definiert als Ein Majority-Gatter ist dabei ein Gatter, das genau dann 1 ausgibt, wenn mehr als die Hälfte der Eingänge den Wert 1 haben. (de) En informatique théorique, et plus précisément en théorie de la complexité, TC est la classe de complexité des problèmes de décision reconnus par des circuits avec seuil. Ce sont des circuits booléens avec des portes ET, des portes OU et des (en). Pour un entier i fixé, la classe TCi est la classe des langages reconnus par une famille de circuits avec seuil de profondeur , de taille , et avec arité non bornée. La classe TC est (fr) In theoretical computer science, and specifically computational complexity theory and circuit complexity, TC is a complexity class of decision problems that can be recognized by threshold circuits, which are Boolean circuits with AND, OR, and Majority gates. For each fixed i, the complexity class TCi consists of all languages that can be recognized by a family of threshold circuits of depth , polynomial size, and unbounded fan-in. The class TC is defined via (en) |
| dbo:wikiPageID | 26200497 (xsd:integer) |
| dbo:wikiPageLength | 2895 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 918694245 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Decision_problem dbr:OR_gate dbr:NC_(complexity) dbr:Complexity_class dbr:Computational_complexity_theory dbr:Theoretical_computer_science dbr:Fan-in dbc:Complexity_classes dbr:AC_(complexity) dbr:AND_gate dbc:Circuit_complexity dbr:Boolean_circuit dbr:Polynomial dbr:Circuit_complexity dbr:Majority_gate |
| dbp:wikiPageUsesTemplate | dbt:Cite_book dbt:Reflist dbt:ComplexityClasses |
| dct:subject | dbc:Complexity_classes dbc:Circuit_complexity |
| rdf:type | yago:WikicatComplexityClasses yago:Abstraction100002137 yago:Class107997703 yago:Collection107951464 yago:Group100031264 |
| rdfs:comment | In der Komplexitätstheorie, speziell der , ist TC eine Komplexitätsklasse und TCi eine Hierarchie von Komplexitätsklassen. Für jedes enthält TCi die formalen Sprachen, die von Schaltkreisfamilien mit Tiefe , polynomieller Größe, und Und-, Oder-, und mit unbeschränktem Fan-In erkannt werden. Die Definition erweitert damit die Klassen ACi, die keine Majority-Gatter erlaubt. Die Klasse TC ist dann definiert als Ein Majority-Gatter ist dabei ein Gatter, das genau dann 1 ausgibt, wenn mehr als die Hälfte der Eingänge den Wert 1 haben. (de) En informatique théorique, et plus précisément en théorie de la complexité, TC est la classe de complexité des problèmes de décision reconnus par des circuits avec seuil. Ce sont des circuits booléens avec des portes ET, des portes OU et des (en). Pour un entier i fixé, la classe TCi est la classe des langages reconnus par une famille de circuits avec seuil de profondeur , de taille , et avec arité non bornée. La classe TC est (fr) In theoretical computer science, and specifically computational complexity theory and circuit complexity, TC is a complexity class of decision problems that can be recognized by threshold circuits, which are Boolean circuits with AND, OR, and Majority gates. For each fixed i, the complexity class TCi consists of all languages that can be recognized by a family of threshold circuits of depth , polynomial size, and unbounded fan-in. The class TC is defined via (en) |
| rdfs:label | TC (Komplexitätsklasse) (de) TC (complexité) (fr) TC (complexity) (en) |
| owl:sameAs | freebase:TC (complexity) yago-res:TC (complexity) wikidata:TC (complexity) dbpedia-de:TC (complexity) dbpedia-fr:TC (complexity) https://global.dbpedia.org/id/2EwvH |
| prov:wasDerivedFrom | wikipedia-en:TC_(complexity)?oldid=918694245&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:TC_(complexity) |
| is dbo:wikiPageDisambiguates of | dbr:TC |
| is dbo:wikiPageWikiLink of | dbr:TC dbr:TC0 dbr:Circuit_(computer_science) |
| is foaf:primaryTopic of | wikipedia-en:TC_(complexity) |