|
|||||
|
|
A counterexample to a conjecture of Schnorr referring to monotone networks |
|
| Authors: | Ingo Wegener |
| Affiliation: | Facultät für Mathematik, Universität Bielefeld 4800 Bielefeld 1, F.R.G. |
| Abstract: | Schnorr[1] proved a lower bound on the number of additions in monotone computations of rational polynomials. He conjectured a similar lower bound on the number of ∨-gates in monotone networks computing monotone Boolean functions. We disprove this conjecture. |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ | |