|
On the computational power of depth 2 circuits with threshold and modulo gates
Krause, Matthias
;
Pudlák, Pavel
|
URL:
|
https://eccc.weizmann.ac.il/report/1994/023/
|
|
Dokumenttyp:
|
Arbeitspapier
|
|
Erscheinungsjahr:
|
1994
|
|
Titel einer Zeitschrift oder einer Reihe:
|
Electronic Colloquium on Computational Complexity : ECCC
|
|
Band/Volume:
|
TR94-023
|
|
Ort der Veröffentlichung:
|
Trier
|
|
Verlag:
|
Universität Trier
|
|
ISSN:
|
1433-8092
|
|
Sprache der Veröffentlichung:
|
Englisch
|
|
Einrichtung:
|
Fakultät für Wirtschaftsinformatik und Wirtschaftsmathematik > Theoretische Informatik (Krause 1996-)
|
|
Fachgebiet:
|
004 Informatik
|
|
Abstract:
|
We investigate the computational power of depth two circuits consisting of MODr--gates at the bottom and a threshold gate at the top (for short, threshold--MODr circuits) and circuits with two levels of MOD gates (MODp-MODq circuits.) In particular, we will show the following results
(i) For all prime numbers p and integers qr it holds that if p divides r but not q then all threshold--MODq circuits for MODr have exponentially many nodes.
(ii) For all integers r all problems computable by depth two ANDORNOT --circuits of (quasi) polynomial size can be represented by threshold--MODr circuits with (quasi)poly\-no\-mially many edges.
(iii) There is a problem computable by depth three ANDORNOT --circuits of linear size and constant bottom fan--in which for all r needs
threshold--MODr circuits with exponentially many nodes.
(iv) For pr different primes, and q2 k positive integers, where p does not divide q every MODpk-MODq circuit for MODr has exponentially many nodes...
|
|
Zusätzliche Informationen:
|
Online-Ressource
|
 | Dieser Datensatz wurde nicht während einer Tätigkeit an der Universität Mannheim veröffentlicht, dies ist eine Externe Publikation. |
 Suche Autoren in
Sie haben einen Fehler gefunden? Teilen Sie uns Ihren Korrekturwunsch bitte hier mit: E-Mail
Actions (login required)
 |
Eintrag anzeigen |
|
|
