AC0 (original) (raw)

About DBpedia

La classe de complexitat AC0 és usada en complexitat de circuits. És la classe més petita a la jerarquia AC i consisteix en totes les famílies de circuits de profunditat O(1) i mida polinòmica, amb portes AND i OR amb fan-in il·limitat (només es permeten portes NOT a les entrades). Per tant conté la classe NC0, que conté portes amb fan-in limitat. La suma i resta d'enters son computables a AC0, però la multiplicació i la divisió no ho son (almenys sota la representació binaria o base 10 d'enters).

thumbnail

Property Value
dbo:abstract في علم التعقيد الحسابي AC0 هو قسم كل المسائل التي يمكن أن تُحل بواسطة دوائر بوليانية عمقها(depth) ثابت وحجمها(size) كثير حدود وعدد اطراف الدخل(fan-in) غير محدود (بما أن الحجم محدود بواسطة كثير حدود فإن عدد اطراف الدخل محدود ليكون كذلك كثير حدود) , هذا القسم هو الاصغر في هرم AC ويحوي القسم NC0 وهو قسم له نفس التعريف إلا أن عدد اطراف الدخل(fan-in) محدود . في 1984 فورست ,ساكس وسبسر برهنوا أن حساب الزوجية لعدد مُعطى ليس تابعا للقسم حتى عندما لا تكون الدوائر موحدة (nonuniform) , وبهذا فانه تبين أنَّ بمساعدة هذه النظرية نستنج أنه يوجد أوركل (مُوحي) الذي يفصل بيسبايس عن أس هيدروجيني أي انه PH≠PSPACE حسب هذا الاوراكل . عمليات الحساب مثل الجمع والطرح تابعة لهذا القسم اما الضرب فلا يتبع . (ar) La classe de complexitat AC0 és usada en complexitat de circuits. És la classe més petita a la jerarquia AC i consisteix en totes les famílies de circuits de profunditat O(1) i mida polinòmica, amb portes AND i OR amb fan-in il·limitat (només es permeten portes NOT a les entrades). Per tant conté la classe NC0, que conté portes amb fan-in limitat. La suma i resta d'enters son computables a AC0, però la multiplicació i la divisió no ho son (almenys sota la representació binaria o base 10 d'enters). (ca) AC0 is a complexity class used in circuit complexity. It is the smallest class in the AC hierarchy, and consists of all families of circuits of depth O(1) and polynomial size, with unlimited-fanin AND gates and OR gates (we allow NOT gates only at the inputs). It thus contains NC0, which has only bounded-fanin AND and OR gates. (en) AC0 ist eine Komplexitätsklasse in der , einem Teilgebiet der Komplexitätstheorie.Sie enthält alle Funktionen, die von Schaltkreisfamilien mit Tiefe O(1) und polynomieller Größe mit Und-Gattern und Oder-Gattern mit unbeschränktem Fan-In, und eventuell Nicht-Gattern an den Eingängen berechnet werden können. Sie ist die kleinste Klasse in der AC-Hierarchie und liegt über , das nur Gatter mit beschränktem Fan-In erlaubt. In der deskriptiven Komplexitätstheorie entspricht -uniformes AC0 der deskriptiven Klasse +BIT der Sprachen, die in Logik erster Stufe mit dem beschrieben werden können, der Klasse FO(+, ), und der . 1984 zeigten Furst, Saxe und Sipser, dass die Parity-Funktion nicht in AC0 liegt. Daraus folgt, dass auch die -Funktion nicht in AC0 liegt. Daraus folgt, dass AC0 ungleich ist. Addition und Subtraktion ganzer Zahlen liegen in AC0, Multiplikation dagegen nicht (zumindest mit den gewöhnlichen Darstellungen zur Basis 2 oder 10). Nimmt man zusätzlich zu UND, AND, NOT Gattern allgemeine modulare Gatter hinzu, hat man die Komplexitätsklasse ACC0. Dabei sind Mod-Gatter (modulare Gatter) Verallgemeinerungen von XOR-Gattern: bei einem mod m Gatter mit n Eingängen ist das Output genau dann Null falls die Anzahl der Einsen in den Inputs ein Vielfaches von m ist (für m=2 ergibt sich das XOR-Gatter). (de) En théorie de la complexité, AC0 est une classe de complexité définie par des circuits booléens de profondeur constante. Elle fait partie de la hiérarchie AC. La classe AC0 contient l'addition, mais pas la fonction parité, la multiplication ou le prédicat de primalité (voir plus bas). (fr) AC0 è una classe di complessità usata nella complessità dei circuiti. È la classe più piccola della gerarchia AC, e consiste di tutte le famiglie di circuiti che hanno profondità O(1) e dimensione polinomiale, con porte AND e porte OR con numero massimo di linee d'ingresso illimitato (fan-in) (ammettiamo le porte NOT soltanto alle entrate). Essa perciò contiene NC0, che ha soltanto porte AND e OR con numero massimo di linee d'ingresso limitato. Da un punto di vista della complessità descrittiva, AC0 in DLOGTIME è uguale alla classe descrittiva +BIT di tutti i linguaggi descrivibili in una logica del primo ordine con l'aggiunta dell', o alternativamente da FO(+, ), o da una macchina di Turing nella . Nel 1984 Furst, Saxe e Sipser dimostrarono che calcolare la di un'entrata non può essere decisa da nessun circuito AC0, anche con la non uniformità. Ne consegue che AC0 non è uguale a , perché una famiglia di circuiti nell'ultima classe può computare la parità. Limiti più precisi conseguono dal . Usandoli, è stato dimostrato che c'è una separazione mediante oracolo tra e PSPACE. L'addizione e la sottrazione degli interi sono computabili in AC0, ma la moltiplicazione no (almeno, non in base alle abituali rappresentazioni binarie o in base 10 degli interi). (it) AC 0 jest klasą złożoności stosowaną w złożoności obliczeniowej obwodów logicznych. Jest to najmniejsza klasa w hierarchii AC i składa się ze wszystkich rodzin obwodów o głębokości O(1) i wielkości wielomianowej, z nieograniczonym stopniem wejścia bramek AND i bramek OR (dopuszczamy bramki NIE tylko na wejściach). W ten sposób zawiera NC0, który ma tylko ograniczony stopień wejścia bramek AND i OR. (pl)
dbo:thumbnail wiki-commons:Special:FilePath/Diagram_of_an_AC0_Circuit.svg?width=300
dbo:wikiPageID 7400698 (xsd:integer)
dbo:wikiPageLength 4074 (xsd:nonNegativeInteger)
dbo:wikiPageRevisionID 1069127234 (xsd:integer)
dbo:wikiPageWikiLink dbr:FO_(complexity) dbr:DLOGTIME dbr:NOT_gate dbr:OR_gate dbr:NC_(complexity) dbr:LH_(complexity) dbr:Complexity_class dbr:Parity_function dbr:P/poly dbr:Fanin dbr:PSPACE dbr:Formal_language dbc:Complexity_classes dbr:AC_(complexity) dbr:AND_gate dbc:Circuit_complexity dbr:BIT_predicate dbr:Polynomial_hierarchy dbr:Circuit_complexity dbr:Michael_Sipser dbr:Turing_machine dbr:Uniformity_(complexity) dbr:Unary_language dbr:Switching_lemma dbr:Descriptive_complexity dbr:File:Diagram_of_an_AC0_Circuit.svg
dbp:wikiPageUsesTemplate dbt:Reflist dbt:ComplexityClasses
dct:subject dbc:Complexity_classes dbc:Circuit_complexity
gold:hypernym dbr:Class
rdf:type yago:WikicatComplexityClasses yago:Abstraction100002137 yago:Class107997703 yago:Collection107951464 yago:Group100031264
rdfs:comment La classe de complexitat AC0 és usada en complexitat de circuits. És la classe més petita a la jerarquia AC i consisteix en totes les famílies de circuits de profunditat O(1) i mida polinòmica, amb portes AND i OR amb fan-in il·limitat (només es permeten portes NOT a les entrades). Per tant conté la classe NC0, que conté portes amb fan-in limitat. La suma i resta d'enters son computables a AC0, però la multiplicació i la divisió no ho son (almenys sota la representació binaria o base 10 d'enters). (ca) AC0 is a complexity class used in circuit complexity. It is the smallest class in the AC hierarchy, and consists of all families of circuits of depth O(1) and polynomial size, with unlimited-fanin AND gates and OR gates (we allow NOT gates only at the inputs). It thus contains NC0, which has only bounded-fanin AND and OR gates. (en) En théorie de la complexité, AC0 est une classe de complexité définie par des circuits booléens de profondeur constante. Elle fait partie de la hiérarchie AC. La classe AC0 contient l'addition, mais pas la fonction parité, la multiplication ou le prédicat de primalité (voir plus bas). (fr) AC 0 jest klasą złożoności stosowaną w złożoności obliczeniowej obwodów logicznych. Jest to najmniejsza klasa w hierarchii AC i składa się ze wszystkich rodzin obwodów o głębokości O(1) i wielkości wielomianowej, z nieograniczonym stopniem wejścia bramek AND i bramek OR (dopuszczamy bramki NIE tylko na wejściach). W ten sposób zawiera NC0, który ma tylko ograniczony stopień wejścia bramek AND i OR. (pl) في علم التعقيد الحسابي AC0 هو قسم كل المسائل التي يمكن أن تُحل بواسطة دوائر بوليانية عمقها(depth) ثابت وحجمها(size) كثير حدود وعدد اطراف الدخل(fan-in) غير محدود (بما أن الحجم محدود بواسطة كثير حدود فإن عدد اطراف الدخل محدود ليكون كذلك كثير حدود) , هذا القسم هو الاصغر في هرم AC ويحوي القسم NC0 وهو قسم له نفس التعريف إلا أن عدد اطراف الدخل(fan-in) محدود . عمليات الحساب مثل الجمع والطرح تابعة لهذا القسم اما الضرب فلا يتبع . (ar) AC0 ist eine Komplexitätsklasse in der , einem Teilgebiet der Komplexitätstheorie.Sie enthält alle Funktionen, die von Schaltkreisfamilien mit Tiefe O(1) und polynomieller Größe mit Und-Gattern und Oder-Gattern mit unbeschränktem Fan-In, und eventuell Nicht-Gattern an den Eingängen berechnet werden können. Sie ist die kleinste Klasse in der AC-Hierarchie und liegt über , das nur Gatter mit beschränktem Fan-In erlaubt. (de) AC0 è una classe di complessità usata nella complessità dei circuiti. È la classe più piccola della gerarchia AC, e consiste di tutte le famiglie di circuiti che hanno profondità O(1) e dimensione polinomiale, con porte AND e porte OR con numero massimo di linee d'ingresso illimitato (fan-in) (ammettiamo le porte NOT soltanto alle entrate). Essa perciò contiene NC0, che ha soltanto porte AND e OR con numero massimo di linee d'ingresso limitato. (it)
rdfs:label AC0 (ar) AC0 (ca) AC0 (de) AC0 (en) AC0 (fr) AC0 (it) AC0 (pl)
owl:sameAs freebase:AC0 yago-res:AC0 wikidata:AC0 dbpedia-ar:AC0 dbpedia-ca:AC0 dbpedia-de:AC0 dbpedia-fr:AC0 dbpedia-it:AC0 dbpedia-pl:AC0 dbpedia-vi:AC0 https://global.dbpedia.org/id/2gNdM
prov:wasDerivedFrom wikipedia-en:AC0?oldid=1069127234&ns=0
foaf:depiction wiki-commons:Special:FilePath/Diagram_of_an_AC0_Circuit.svg
foaf:isPrimaryTopicOf wikipedia-en:AC0
is dbo:wikiPageRedirects of dbr:AC0_(complexity)
is dbo:wikiPageWikiLink of dbr:Proof_complexity dbr:List_of_complexity_classes dbr:Primality_test dbr:Descriptive_complexity_theory dbr:Propositional_proof_system dbr:Pseudorandom_generator dbr:Star-free_language dbr:Conjunctive_query dbr:LH_(complexity) dbr:Berman–Hartmanis_conjecture dbr:Stephen_Cook dbr:Majority_function dbr:Succinct_game dbr:Fusion_tree dbr:Gadget_(computer_science) dbr:Janson_inequality dbr:Graph_canonization dbr:Regular_language dbr:ACC0 dbr:AC_(complexity) dbr:TC0 dbr:CC_(complexity) dbr:Circuit_Value_Problem dbr:Circuit_complexity dbr:NP-completeness dbr:Nati_Linial dbr:Natural_proof dbr:Riemann_mapping_theorem dbr:AC0_(complexity)
is foaf:primaryTopic of wikipedia-en:AC0