Random problems |
| |
Institution: | Departments of Electrical Engineering and Computer Science, California Institute of Technology, Pasadena, California 91125, USA |
| |
Abstract: | A problem (a Boolean function f: {0, 1}N → {0, 1}) is characterized by its randomness (à la Kolmogorov) R(f) and its entropy (à la Shannon) H(f). Random problems have large values of R(f) and are a good model for many natural pattern recognition problems. R(f) and H(f) are shown to be lower and upper bounds, respectively, for a minimum-size circuit that computes f False entropy, namely the hidden structure of a problem, is related to the difference between H(f) and R(f). |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|