There is a resource bounded version of Kolmogorov complexity. It might even be a more useful measure for certain things. For example, a simple enumeration can prove any arithmetical statement that can be proved, but it can take time exponential in the size of the solution. With some resource weightings you might get a better idea of how hard the problem is in actual practice.