Generalized Kolmogorov complexity in relativized separations

We describe several developments of a technique, due to Hartmanis, that uses Kolmogorov complexity to prove the existence of relativizations separating complexity classes. The main advantage of these proofs is that they clearly show the limitations of certain classes of oracle machines and the relevance of these limitations for the proof. Such limitations refer to the extent to which the machines defining the class are able to process Kolmogorov-complex structures.Postprint (published version