The mathematical theory of computation has given rise to two significant approaches to the informal concept of “complexity.” Kolmogorov complexity, typically used as a measure for a single object like a string or sequence, assesses the information required to describe the object. On the other hand, computational complexity, usually a measure for a set of objects, gauges the computational resources needed to recognize or produce elements within the set.
Exploring the relationship between these two complexity measures has been a subject of consideration for over two decades, yielding numerous interesting and profound observations. In March 1990, the Symposium on the Theory and Application of Minimal-Length Encoding took place at Stanford University as part of the AAAI 1990 Spring Symposium Series. Some sessions of the symposium focused on Kolmogorov complexity and its connections to computational complexity theory, featuring excellent expository talks. Recognizing the importance of the material, there was a desire to share these talks with the computer science research community. As a result, the speakers from those sessions were approached to contribute survey papers based on their talks. Five speakers accepted the invitation, and their contributions form the content of this book.
Download
See also
- Software Exorcism: A Handbook for Debugging and Optimizing Legacy Code by Bill Blunden (2003)
- Hormones and the Endocrine System: Textbook of Endocrinology by Bernhard Kleine (2016)
- Genetics: A Conceptual Approach 6e by Benjamin A. Pierce (2017)
- A Functional Approach to Java by Ben Weidig (2022)
- Calculus of variations and optimal control by Amol Sasan (2005)