| 布尔函数线路复杂度的一个新的下界 |
| |
| 引用本文： | 金人超,宋恩民.布尔函数线路复杂度的一个新的下界[J].计算机学报,1994,17(5):376-379. |
| |
| 作者姓名： | 金人超 宋恩民 |
| |
| 作者单位： | 机电部武汉计算机外设研究所，华中理工大学计算机科学与工程系 |
| |
| 摘 要： | 布尔函数的线路复杂下界问题与Ｐ＝？ＮＰ问题有密切关系，若证明了ＮＰ中某问题的线路复杂度是非多项式的，则Ｐ≠ＮＰ。但证明了一个具体的布尔函数具有非线性的线路复杂度下界却是计算复杂性理论中最难的问题之一。迄今此问题的最好结果是由Ｎ．Ｂｌｕｍ于１８９４年给出的，他证明了一个布尔函数具有３ｎ－３的线路复杂度下界。本文针对同一个布尔函数，给出一个更好的下界３ｎ＋１。
|
| 关 键 词： | 布尔函数 线路复杂度 下界 |
A NEW LOWER BOUND FOR THE NETWORK COMPLEXITY OF A BOOLEAN FUNCTION |
| |
| Jin Renchao.A NEW LOWER BOUND FOR THE NETWORK COMPLEXITY OF A BOOLEAN FUNCTION[J].Chinese Journal of Computers,1994,17(5):376-379. |
| |
| Authors: | Jin Renchao |
| |
| Abstract: | N.Blum(1984) proved the 3n-3 lower bound for the network complexity of an explicit Boolean function.A 3n 1 lower bound for the network complexity of the same function is obtained in the paper. |
| |
| Keywords: | Boolean function network complexity lower bound |
| 本文献已被 CNKI 维普 等数据库收录！ |
