AC0
http://dbpedia.org/resource/AC0 an entity of type: WikicatComplexityClasses
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).
rdf:langString
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.
rdf:langString
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).
rdf:langString
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.
rdf:langString
في علم التعقيد الحسابي AC0 هو قسم كل المسائل التي يمكن أن تُحل بواسطة دوائر بوليانية عمقها(depth) ثابت وحجمها(size) كثير حدود وعدد اطراف الدخل(fan-in) غير محدود (بما أن الحجم محدود بواسطة كثير حدود فإن عدد اطراف الدخل محدود ليكون كذلك كثير حدود) , هذا القسم هو الاصغر في هرم AC ويحوي القسم NC0 وهو قسم له نفس التعريف إلا أن عدد اطراف الدخل(fan-in) محدود . عمليات الحساب مثل الجمع والطرح تابعة لهذا القسم اما الضرب فلا يتبع .
rdf:langString
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.
rdf:langString
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.
rdf:langString
rdf:langString
AC0
rdf:langString
AC0
rdf:langString
AC0
rdf:langString
AC0
rdf:langString
AC0
rdf:langString
AC0
rdf:langString
AC0
xsd:integer
7400698
xsd:integer
1069127234
rdf:langString
في علم التعقيد الحسابي AC0 هو قسم كل المسائل التي يمكن أن تُحل بواسطة دوائر بوليانية عمقها(depth) ثابت وحجمها(size) كثير حدود وعدد اطراف الدخل(fan-in) غير محدود (بما أن الحجم محدود بواسطة كثير حدود فإن عدد اطراف الدخل محدود ليكون كذلك كثير حدود) , هذا القسم هو الاصغر في هرم AC ويحوي القسم NC0 وهو قسم له نفس التعريف إلا أن عدد اطراف الدخل(fan-in) محدود . في 1984 فورست ,ساكس وسبسر برهنوا أن حساب الزوجية لعدد مُعطى ليس تابعا للقسم حتى عندما لا تكون الدوائر موحدة (nonuniform) , وبهذا فانه تبين أنَّ بمساعدة هذه النظرية نستنج أنه يوجد أوركل (مُوحي) الذي يفصل بيسبايس عن أس هيدروجيني أي انه PH≠PSPACE حسب هذا الاوراكل . عمليات الحساب مثل الجمع والطرح تابعة لهذا القسم اما الضرب فلا يتبع .
rdf:langString
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).
rdf:langString
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.
rdf:langString
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).
rdf:langString
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).
rdf:langString
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).
rdf:langString
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.
xsd:nonNegativeInteger
4074
