AC (complexity) (original) (raw)
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
| Property | Value |
|---|---|
| dbo: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) |
| dbo:wikiPageID | 7401755 (xsd:integer) |
| dbo:wikiPageLength | 2769 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 598406179 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Cambridge_University_Press dbr:ACC_(complexity) dbr:OR_gate dbr:Modulo_operation dbr:NC_(complexity) dbr:Complexity_class dbr:Fanin dbr:Alternating_Turing_machine dbr:Formal_language dbc:Complexity_classes dbr:AC0 dbr:AND_gate dbc:Circuit_complexity dbr:Boolean_circuit dbr:Polynomial dbr:Circuit_complexity dbr:Springer-Verlag |
| dbp:wikiPageUsesTemplate | dbt:Citation 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 | 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) |
| 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) |
| owl:sameAs | freebase:AC (complexity) yago-res:AC (complexity) wikidata:AC (complexity) dbpedia-ca:AC (complexity) dbpedia-de:AC (complexity) dbpedia-fr:AC (complexity) dbpedia-it:AC (complexity) dbpedia-pl:AC (complexity) https://global.dbpedia.org/id/kydC |
| prov:wasDerivedFrom | wikipedia-en:AC_(complexity)?oldid=598406179&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:AC_(complexity) |
| is dbo:wikiPageDisambiguates of | dbr:AC |
| is dbo:wikiPageRedirects of | dbr:AC_hierarchy |
| is dbo:wikiPageWikiLink of | dbr:List_of_complexity_classes dbr:Descriptive_complexity_theory dbr:NC_(complexity) dbr:NL_(complexity) dbr:LOGCFL dbr:Stephen_Cook dbr:Complexity_class dbr:Computational_complexity_theory dbr:TC_(complexity) dbr:AC dbr:AC1 dbr:AC0 dbr:Boolean_circuit dbr:Circuit_(computer_science) dbr:Circuit_complexity dbr:Fixed-point_logic dbr:AC_hierarchy |
| is foaf:primaryTopic of | wikipedia-en:AC_(complexity) |