On another Boolean matrix |
| |
| Authors: | Nicholas Pippenger |
| |
| Affiliation: | Mathematical Sciences Department, IBM Thomas J. Watson Research Center, Yorktown Heights, NY 10598, U.S.A. |
| |
| Abstract: | In his paper “On a Boolean matrix”, Nechiporuk gave an explicit example of a set of n homogeneous monotone Boolean functions of the first degree in n variables that require Ω(n3/2) two-input gates in any monotone Boolean network computing them. In this note we show how this can be extended to Ω(n5/3) two-input gates. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
