Kolmogorov complexity and computational complexity
Springer-Verlag, 1992 - Computers - 105 pages
There 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.
9 pages matching Theorem 13 in this book
Results 1-3 of 9
What people are saying - Write a review
On Sets with Small Information Content
Kolmogorov Complexity Complexity Cores
3 other sections not shown
Other editions - View all
Information and Randomness: An Algorithmic Perspective
Limited preview - 2002
Applications of Time-Bounded Kolmogorov Complexity in Complexity ...
In Watanabe, O., editor, Kolmogorov complexity and computational complexity, pages 6--22. EATCS Monographs on Theoretical Computer Science, ...
Effective prediction and its computational complexity
Allender, E. (1992): Applications of Time-Bounded Kolmogorov Complexity in Complexity Theory, Kolmogorov Complexity and Computational Complexity, ...
Watanabe O. (ed.) — Kolmogorov Complexity and Computational ...
This book consists of four survey papers concerning these recent studies on resource-bounded Kolmogorov complexity and computational complexity. ...
lib.mexmat.ru/ books/ 12964
In O. Watanabe, editor, Kolmogorov complexity and computational complexity, pages 6-22. EATCS Monographs on Theoretical Computer Science, Springer, 1992. ...
www.idsia.ch/ ~juergen/ toesv2/ node47.html
Theoretical Computer Science : Effective simultaneous ...
Kolmogorov Complexity and Computational Complexity, Springer, Berlin (1992). 1 Partially supported by the Russian Foundation for Basic Research. ...
linkinghub.elsevier.com/ retrieve/ pii/ S0304397501000974
Phys. Rev. E 64, 016209 (2001): Rapp et al. - Effective ...
Kolmogorov Complexity and Computational Complexity, edited by O. Watanabe (Springer-Verlag, Berlin, 1992). P. Grassberger, Int. J. Theor. Phys. ...
link.aps.org/ doi/ 10.1103/ PhysRevE.64.016209
arxiv:quant-ph/0011122v2 20 Dec 2000
Technical Report IDSIA-20-00, Version 2.0; 20 Dec 2000. Minor revision of Version 1.0 , quant-ph/0011122. ALGORITHMIC THEORIES OF EVERYTHING ...
arxiv.org/ pdf/ quant-ph/ 0011122
Bibliographie 1. ABU-MOSTAFA, ys : The complexity of information ...
Kolmogorov Complexity and Computational Complexity,. EATCS, Springer-Verlag, Berlin, 1992. 393. WATANABE, S. : Knowing and guessing, John Wiley, New York, ...
www.syscope.net/ info/ TCI_biblio.PDF
Consulta de catŕlegs de l'UPV
Títol, Kolmogorov complexity and computational complexity / ed. Osamu Watanabe. Publicació, Berlin [etc.] : Springer, cop. 1992 ...
www.upv.es/ pls/ obib/ sic_opac.FichaCampos?p_vista=&