| 关于布尔线路计算模型的注记 |
| |
| 引用本文： | 宋恩民,黄文奇.关于布尔线路计算模型的注记[J].华中科技大学学报(自然科学版),1992(5). |
| |
| 作者姓名： | 宋恩民 黄文奇 |
| |
| 作者单位： | 华中理工大学计算机科学与工程系
(宋恩民)，华中理工大学计算机科学与工程系(黄文奇) |
| |
| 基金项目： | 国家自然科学基金资助项目 |
| |
| 摘 要： | 本文给出了一种布尔线路的编码方案.证明了有关布尔线路编码中的两个定理,其中定理1表明对布尔线路这种计算模型,没有类似于图灵机的递归式定理那样的结论;定理2表明对于布尔线路计算模型,存在类似于图灵机中的Smn定理那样的结论.另外,本文还证明了一个有关布尔线路宽度的定理,此定理表明,布尔线路的宽度与计算能力无关.
|
| 关 键 词： | 布尔函数 布尔线路 计算模型 编码 |
Notes on the Boolean Circuit Computation Model |
| |
| Song Enmin Huang Wenqi.Notes on the Boolean Circuit Computation Model[J].JOURNAL OF HUAZHONG UNIVERSITY OF SCIENCE AND TECHNOLOGY.NATURE SCIENCE,1992(5). |
| |
| Authors: | Song Enmin Huang Wenqi |
| |
| Institution: | Song Enmin Huang Wenqi |
| |
| Abstract: | Research on the Boolean circuit computation model is a promising approach to solving the P = ? NP problem. An encoding scheme on the Boolean circuit is given and two theorems about the encoding of the Boolean circuit have been obtained. Some relationships between the two computation models are revealed by the two theorems. A theorem about the Boolean circuit width is also obtained, which shows that the width of a Boolean circuit cannot demonstrate the complexity of the function which is computed by the Boolean circuit. |
| |
| Keywords: | Boolean function Boolean circuit computation model encoding |
| 本文献已被 CNKI 等数据库收录！ |
