## Kolmogorov complexity and computational complexityThere are many ways to measure the complexity of a given object, but there are two measures of particular importance in the theory of computing: One is Kolmogorov complexity, which measures the amount of information necessary to describe an object. Another is computational complexity, which measures the computational resources necessary to recognize (or produce) an object. The relation between these two complexity measures has been studied since the 1960s. More recently, the more generalized notion of resource bounded Kolmogorov complexity and its relation to computational complexity have received much attention. Now many interesting and deep observations on this topic have been established. This book consists of four survey papers concerning these recent studies on resource bounded Kolmogorov complexity and computational complexity. It also contains one paper surveying several types of Kolmogorov complexity measures. The papers are based on invited talks given at the AAAI Spring Symposium on Minimal-Length Encoding in 1990. The book is the only collection of survey papers on this subject and provides fundamental information for researchers in the field. |

### What people are saying - Write a review

We haven't found any reviews in the usual places.

### Contents

Introduction | 1 |

On Sets with Small Information Content | 20 |

Kolmogorov Complexity Complexity Cores | 43 |

Copyright | |

3 other sections not shown

### Other editions - View all

### Common terms and phrases

algorithm Allender Balcazar binary bounded Kolmogorov complexity class of sets complexity classes complexity cores complexity of sets computable in polynomial computational complexity theory consider constant defined denoted dense sets encoded exists exponential EXPSPACE finite four entropies hard language Hartmanis infinite K-random Kolmogorov random language A C 0,1 language in ESPACE lower bound Martin-L6f notation notion nowhere-dense set NP(A O(logn oracle machine oracle set Osamu Watanabe output P-printable P/poly paper plexity polynomial-size circuits polynomial-time hierarchy predicate probability Proc pseudo-random number pseudorandom PSPACE query random number random oracle random sequences random strings recursive relative resource-bounded self-producible circuits set of strings sets with small SIAM small generalized Kolmogorov small information content space bound space-bounded Kolmogorov complexity sparse set statistical test strings of length subset tally set test F Theorem 13 truth-table reducible Turing machine Turing reducible universal test universal Turing machine upper bound Watanabe