Random problems (Q1113868)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Random problems |
scientific article; zbMATH DE number 4081454
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Random problems |
scientific article; zbMATH DE number 4081454 |
Statements
Random problems (English)
0 references
1988
0 references
A problem (a Boolean function \(f:\{0,1\}^ N\to \{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).
0 references
randomness
0 references
entropy
0 references
pattern recognition
0 references
