Kolmogorov Complexity and Computational Complexity
The mathematical theory of computation has given rise to two important ap proaches to the informal notion of "complexity": Kolmogorov complexity, usu ally a complexity measure for a single object such as a string, a sequence etc., measures the amount of information necessary to describe...
| Other Authors: | |
|---|---|
| Format: | eBook |
| Language: | English |
| Published: |
Berlin, Heidelberg
Springer Berlin Heidelberg
1992, 1992
|
| Edition: | 1st ed. 1992 |
| Series: | Monographs in Theoretical Computer Science. An EATCS Series
|
| Subjects: | |
| Online Access: | |
| Collection: | Springer Book Archives -2004 - Collection details see MPG.ReNa |
Table of Contents:
- Applications of Time-Bounded Kolmogorov Complexity in Complexity Theory
- On Sets with Small Information Content
- Kolmogorov Complexity, Complexity Cores, and the Distribution of Hardness
- Resource Bounded Kolmogorov Complexity and Statistical Tests
- Complexity and Entropy: An Introduction to the Theory of Kolmogorov Complexity