A note on the power of majority gates and modular gates
1995; Elsevier BV; Volume: 53; Issue: 6 Linguagem: Inglês
10.1016/0020-0190(94)00221-j
ISSN1872-6119
Autores Tópico(s)semigroups and automata theory
ResumoDepth-two Boolean circuits consisting of a majority gate at the top and MODr gates at the bottom (where r is an arbitrary fixed integer) are considered. It is shown that if t has a prime factor that does not divide r, then such circuits that check if ∑i = 1n xi ≡ 0 mod t must have exponential size.
Referência(s)