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.
Search Authors in