An Entity of Type: Class107997703, from Named Graph: http://dbpedia.org, within Data Space: dbpedia.org

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

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
dbp:wikiPageUsesTemplate
dcterms:subject
rdf:type
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
prov:wasDerivedFrom
foaf:isPrimaryTopicOf
is dbo:wikiPageDisambiguates of
is dbo:wikiPageWikiLink of
is foaf:primaryTopic of
Powered by OpenLink Virtuoso    This material is Open Knowledge     W3C Semantic Web Technology     This material is Open Knowledge    Valid XHTML + RDFa
This content was extracted from Wikipedia and is licensed under the Creative Commons Attribution-ShareAlike 3.0 Unported License