There is a classical approach to the problem of classifying strings with respect to the difficulty of computing them; in some sense, we look for a definition of the amount of information coded by the string. Intuitively, a difficult string contains a high amount of compactly coded information, and one has to know all this information in order to write down the string. Conversely, an easy string has low information content, and one can describe the string in a compact way, so that from this small description one can obtain enough information to reconstruct the string and write it down. This idea can be formalized as we do in this chapter, giving rise to a different concept of complexity, known as Kolmogorov complexity, which has been succesfully used for proving lower bounds in a more concrete approach to complexity theory.