On the Computational Power of Depth 2 Circuits with Threshold and Modulo Gates
Matthias Krause, Pavel Pudlák · 1994
. We investigate the computational power of depth two circuits consisting of MOD r --gates at the bottom and a threshold gate at the top (for short, threshold--MOD r circuits) and circuits with two levels of MOD gates (MOD p - MOD q circuits.) In particular, we will show the following results (i) For all prime numbers p and integers q; r it holds that if p divides r but not q then all threshold--MOD q circuits for MOD r have exponentially many nodes. (ii) For all integers r all problems computable by depth two fAND;OR;NOTg-- circuits of (quasi) polynomial size can be represented by threshold--MOD r circuits with (quasi)polynomially many edges. (iii) There is a problem computable by depth three fAND;OR;NOTg--circuits of linear size and constant bottom fan--in which for all r needs threshold--MOD r circuits with exponentially many nodes. (iv) For p; r different primes, and q 2; k positive integers, where p does not divide q; every MOD p k -MOD q circuit for MOD ...