Switching functions whose monotone complexity is nearly quadratic |
| |
| Authors: | Ingo Wegener |
| |
| Affiliation: | Fakultät für Mathematik der Universitat Bielefeld, Universitätsstraße 1, 4800 Bielefeld 1, Federal Republic of Germany |
| |
| Abstract: | A sequence of monotone switching functions hn:{0,1}n→ {0,1}n is constructed, such that the monotone complexity of hn grows faster than Ω(n2 log?2n). Previously the best lower bounds of this nature were several Ω(n bounds due to Pratt, Paterson, Mehlhorn and Galil and Savage. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
