About: TC (complexity)     Goto   Sponge   NotDistinct   Permalink

An Entity of Type : yago:Group100031264, within Data Space : dbpedia.demo.openlinksw.com associated with source document(s)
QRcode icon
http://dbpedia.demo.openlinksw.com/describe/?url=http%3A%2F%2Fdbpedia.org%2Fresource%2FTC_%28complexity%29&invfp=IFP_OFF&sas=SAME_AS_OFF

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

AttributesValues
rdf:type
rdfs:label
  • TC (Komplexitätsklasse) (de)
  • TC (complexité) (fr)
  • TC (complexity) (en)
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)
dcterms:subject
Wikipage page ID
Wikipage revision ID
Link from a Wikipage to another Wikipage
sameAs
dbp:wikiPageUsesTemplate
has 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)
prov:wasDerivedFrom
page length (characters) of wiki page
foaf:isPrimaryTopicOf
is Link from a Wikipage to another Wikipage of
is Wikipage disambiguates of
is foaf:primaryTopic of
Faceted Search & Find service v1.17_git139 as of Feb 29 2024


Alternative Linked Data Documents: ODE     Content Formats:   [cxml] [csv]     RDF   [text] [turtle] [ld+json] [rdf+json] [rdf+xml]     ODATA   [atom+xml] [odata+json]     Microdata   [microdata+json] [html]    About   
This material is Open Knowledge   W3C Semantic Web Technology [RDF Data] Valid XHTML + RDFa
OpenLink Virtuoso version 08.03.3330 as of Mar 19 2024, on Linux (x86_64-generic-linux-glibc212), Single-Server Edition (378 GB total memory, 67 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software