About: AC (complexity)     Goto   Sponge   NotDistinct   Permalink

An Entity of Type : yago:Group100031264, within Data Space : dbpedia.org associated with source document(s)
QRcode icon
http://dbpedia.org/describe/?url=http%3A%2F%2Fdbpedia.org%2Fresource%2FAC_%28complexity%29

In circuit complexity, AC is a complexity class hierarchy. Each class, ACi, consists of the languages recognized by Boolean circuits with depth and a polynomial number of unlimited fan-in AND and OR gates. The name "AC" was chosen by analogy to NC, with the "A" in the name standing for "alternating" and referring both to the alternation between the AND and OR gates in the circuits and to alternating Turing machines. The smallest AC class is AC0, consisting of constant-depth unlimited fan-in circuits. The total hierarchy of AC classes is defined as

AttributesValues
rdf:type
rdfs:label
  • AC (Complexitat) (ca)
  • AC (Komplexitätsklasse) (de)
  • AC (complexity) (en)
  • AC (complexité) (fr)
  • AC (complessità) (it)
  • AC (klasa złożoności) (pl)
rdfs:comment
  • En teoria de la complexitat, AC és una jerarquia de classes de complexitat. Cada classe ACi consisteix en els llenguatges reconeguts per un circuit booleà de profunditat i un nombre polinòmic de portes AND, OR i NOT de fan-in il·limitat. El nom AC es va triar per analogia al de la classe NC, amb la A referint-se a "alternant", referint-se a les portes AND i OR organitzades de manera alternativa i a les màquines de Turing alternants. La classe més petita és AC0 ,consistent en els circuits de profunditat constant i fan-in il·limitat. Tota la jerarquia de les classes AC es defineix com (ca)
  • In circuit complexity, AC is a complexity class hierarchy. Each class, ACi, consists of the languages recognized by Boolean circuits with depth and a polynomial number of unlimited fan-in AND and OR gates. The name "AC" was chosen by analogy to NC, with the "A" in the name standing for "alternating" and referring both to the alternation between the AND and OR gates in the circuits and to alternating Turing machines. The smallest AC class is AC0, consisting of constant-depth unlimited fan-in circuits. The total hierarchy of AC classes is defined as (en)
  • En théorie de la complexité, AC est la classe de complexité définie comme l'union des ACi, où ACi est la classe de complexité des problèmes décidés par des circuits booléens de profondeur , de taille polynomiale, dont les portes sont des ET et des OU, de degrés entrants non bornés (en fait, d'autres portes peuvent être autorisés comme des portes "OU exclusif" ou NON car elles sont exprimables, sans changer la complexité, par des ET et des OU). En particulier, AC0 est la classe de complexité des problèmes décidés par des circuits booléens de profondeur constante, de taille polynomiale. (fr)
  • In der Komplexitätstheorie, speziell der , ist AC eine Komplexitätsklasse und ACi eine Hierarchie von Komplexitätsklassen. Für jedes enthält ACi die formalen Sprachen, die von Schaltkreisfamilien mit Tiefe , polynomieller Größe, und Und- und Oder- mit unbeschränktem Fan-In und eventuell Nicht-Gattern an den Eingängen erkannt werden. Die Klasse AC ist dann definiert als Der Name AC wurde in Analogie zu NC gewählt, wobei A für „alternierend“ steht, was sich sowohl auf die Alternation zwischen Und- und Oder-Gattern in AC-Schaltkreisen als auch auf alternierende Turingmaschinen bezieht. (de)
  • Nella complessità dei circuiti, AC è una gerarchia di classi di complessità. Ciascuna classe, ACi, consiste dei linguaggi riconosciuti dai circuiti booleani con profondità e un numero polinomiale di porte AND e OR, con un numero massimo di linee d'ingresso (fan-in) illimitato. Il nome "AC" fu scelto per analogia con NC, con la "A" nel nome che sta per "alternante" e si riferisce sia all'alternanza tra le porte AND e OR nei circuiti sia alle . La classe AC è AC0, che consiste di circuiti con numero massimo di linee d'ingresso illimitato a profondità costante. (it)
  • W złożoności obliczeniowej obwodów logicznych AC jest hierarchią klas złożoności. Każda klasa, ACi, składa się z języków rozpoznawanych przez obwody logiczne z głębokością oraz wielomianową liczbę bramek o nieskończonym stopniu wejścia AND i OR. Nazwę „AC” wybrano analogicznie do NC, przy czym „A” w nazwie oznacza „przemiennie” (alternating) i odnosi się zarówno do naprzemienności bramek AND i OR w obwodach, jak i do naprzemiennych maszyn Turinga. Najmniejszą klasą prądu przemiennego jest prąd zmienny 0, składający się z obwodów logicznych o stałej głębokości i nieskończonym stopniu wejścia. (pl)
dcterms:subject
Wikipage page ID
Wikipage revision ID
Link from a Wikipage to another Wikipage
sameAs
dbp:wikiPageUsesTemplate
has abstract
  • En teoria de la complexitat, AC és una jerarquia de classes de complexitat. Cada classe ACi consisteix en els llenguatges reconeguts per un circuit booleà de profunditat i un nombre polinòmic de portes AND, OR i NOT de fan-in il·limitat. El nom AC es va triar per analogia al de la classe NC, amb la A referint-se a "alternant", referint-se a les portes AND i OR organitzades de manera alternativa i a les màquines de Turing alternants. La classe més petita és AC0 ,consistent en els circuits de profunditat constant i fan-in il·limitat. Tota la jerarquia de les classes AC es defineix com (ca)
  • In der Komplexitätstheorie, speziell der , ist AC eine Komplexitätsklasse und ACi eine Hierarchie von Komplexitätsklassen. Für jedes enthält ACi die formalen Sprachen, die von Schaltkreisfamilien mit Tiefe , polynomieller Größe, und Und- und Oder- mit unbeschränktem Fan-In und eventuell Nicht-Gattern an den Eingängen erkannt werden. Die Klasse AC ist dann definiert als Der Name AC wurde in Analogie zu NC gewählt, wobei A für „alternierend“ steht, was sich sowohl auf die Alternation zwischen Und- und Oder-Gattern in AC-Schaltkreisen als auch auf alternierende Turingmaschinen bezieht. Die kleinste AC-Klasse ist AC0, in der Sprachen liegen, die von Schaltkreisen konstanter Tiefe erkannt werden. Es gilt ; ansonsten ist unbekannt, ob die Hierarchie echt ist. Für jede natürliche Zahl p bezeichnet ACi[p] oder ACCi[p] die Klasse der Probleme, die von ACi-Schaltkreisen plus Modulo p-Gattern erkannt werden. Ein Modulo p-Gatter gibt dabei genau dann 1 aus, wenn die Zahl der Eingaben mit Wert 1 nicht durch p teilbar ist. Die Klassen i sind ähnlich definiert und erlauben beliebige Modulo-Gatter. (de)
  • In circuit complexity, AC is a complexity class hierarchy. Each class, ACi, consists of the languages recognized by Boolean circuits with depth and a polynomial number of unlimited fan-in AND and OR gates. The name "AC" was chosen by analogy to NC, with the "A" in the name standing for "alternating" and referring both to the alternation between the AND and OR gates in the circuits and to alternating Turing machines. The smallest AC class is AC0, consisting of constant-depth unlimited fan-in circuits. The total hierarchy of AC classes is defined as (en)
  • En théorie de la complexité, AC est la classe de complexité définie comme l'union des ACi, où ACi est la classe de complexité des problèmes décidés par des circuits booléens de profondeur , de taille polynomiale, dont les portes sont des ET et des OU, de degrés entrants non bornés (en fait, d'autres portes peuvent être autorisés comme des portes "OU exclusif" ou NON car elles sont exprimables, sans changer la complexité, par des ET et des OU). En particulier, AC0 est la classe de complexité des problèmes décidés par des circuits booléens de profondeur constante, de taille polynomiale. (fr)
  • Nella complessità dei circuiti, AC è una gerarchia di classi di complessità. Ciascuna classe, ACi, consiste dei linguaggi riconosciuti dai circuiti booleani con profondità e un numero polinomiale di porte AND e OR, con un numero massimo di linee d'ingresso (fan-in) illimitato. Il nome "AC" fu scelto per analogia con NC, con la "A" nel nome che sta per "alternante" e si riferisce sia all'alternanza tra le porte AND e OR nei circuiti sia alle . La classe AC è AC0, che consiste di circuiti con numero massimo di linee d'ingresso illimitato a profondità costante. La gerarchia totale delle classi AC è definita come (it)
  • W złożoności obliczeniowej obwodów logicznych AC jest hierarchią klas złożoności. Każda klasa, ACi, składa się z języków rozpoznawanych przez obwody logiczne z głębokością oraz wielomianową liczbę bramek o nieskończonym stopniu wejścia AND i OR. Nazwę „AC” wybrano analogicznie do NC, przy czym „A” w nazwie oznacza „przemiennie” (alternating) i odnosi się zarówno do naprzemienności bramek AND i OR w obwodach, jak i do naprzemiennych maszyn Turinga. Najmniejszą klasą prądu przemiennego jest prąd zmienny 0, składający się z obwodów logicznych o stałej głębokości i nieskończonym stopniu wejścia. Całkowita hierarchia klas AC jest zdefiniowana jako (pl)
prov:wasDerivedFrom
page length (characters) of wiki page
foaf:isPrimaryTopicOf
is Link from a Wikipage to another Wikipage of
is Wikipage redirect 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, 54 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software