The key phrase you are looking for is "resource-bounded Kolmogorov complexity". This paper by Allender, et. al. may be a good starting point. Also, this PhD thesis might provide some helpful background.
Edited to add:
According to the first article, Ko, K.-I. "On the complexity of learning minimum time-bounded Turing machines", SIAM Journal on Computing, 20 (1991) may be even more relevant. In that paper, Ko demonstrates that determining whether or not computing time-bounded Kolmogorov complexity is NP-hard requires non-relativizing techniques.
