New applications of the incompressibility method: Part II
- Author(s): Buhrman, H
- Jiang, T
- Li, M
- Vitányi, P
- et al.
Published Web Locationhttps://doi.org/10.1016/S0304-3975(99)00184-X
The incompressibility method is an elementary yet powerful proof technique. It has been used successfully in many areas (Li and Vitányi, An Introduction to Kolmogorov Complexity and its Applications, Springer, New York, 1997). To further demonstrate its power and elegance we exhibit new simple proofs using the incompressibility method. © 2000 Elsevier Science B.V. All rights reserved.