Information theory and the complexity of boolean functions |
| |
| Authors: | Nicholas Pippenger |
| |
| Affiliation: | (3) CWI, Kruislaan 413, 1098 SJ Amsterdam, The Netherlands |
| |
| Abstract: | This paper explores the connections between two areas pioneered by Shannon: the transmission of information with a fidelity criterion, and the realization of Boolean functions by networks and formulae. We study three phenomena:| 1. |
The effect of the relative number of O's and l's in a function's table on its complexity.
| | 2. |
The effect of the number of unspecified entries in a partially specified function's table on its complexity.
| | 3. |
The effect of the number of errors allowed in the realization of a function on its complexity.
|
Our main result is a precise version of the following statement: |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
