Loading...
Please wait, while we are loading the content...
Similar Documents
On the computational power of depth 2 circuits with threshold and modulo gates (2000).
| Content Provider | CiteSeerX |
|---|---|
| Author | Krause, Matthias Pudlák, Pavel |
| Abstract | We investigate the computational power of depth two circuits consisting of MOD r --gates at the bottom and a threshold gate with arbitrary weights 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 polynomial size have threshold--MOD r circuits with polynomially many edges. (iii) There is a problem computable by depth 3 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 r does not divide q; every MOD p k -MOD q circuit for MOD r has e... |
| File Format | |
| Publisher Date | 2000-01-01 |
| Access Restriction | Open |
| Subject Keyword | Computational Power Threshold Mod Circuit Modulo Gate Mod Gate Mod Circuit Notg Circuit Many Node Arbitrary Weight Positive Integer Prime Number Different Prime Mod Mod Circuit Linear Size Polynomial Size Following Result Threshold Gate Problem Computable Many Edge Constant Bottom Fan |
| Content Type | Text |
