The relationship between both notions plays a crucial role in the area of pseudo-randomness and derandomization. Using these relationships, we obtain hardness results for the set of descriptively random strings (for various Kolmogorov measures). Previously, it was believed that these sets did not have enough structure to capture the power of the complexity classes they naturally live in. In contrast, we show that they *are* complete for these classes.
Joint work with Allender, Buhrman, Koucky, and Ronneburger, to be presented at FOCS 2002.