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/
Document Type: Working paper
Year of publication: 1994
The title of a journal, publication series: Electronic Colloquium on Computational Complexity : ECCC
Volume: TR94-023
Place of publication: Trier
Publishing house: Universität Trier
ISSN: 1433-8092
Publication language: English
Institution: School of Business Informatics and Mathematics > Theoretische Informatik (Krause)
Subject: 004 Computer science, internet
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...
Additional information: Online-Ressource

Dieser Datensatz wurde nicht während einer Tätigkeit an der Universität Mannheim veröffentlicht, dies ist eine Externe Publikation.

Metadata export


+ Search Authors in

+ Page Views

Hits per month over past year

Detailed information

You have found an error? Please let us know about your desired correction here: E-Mail

Actions (login required)

Show item Show item