After reading the nice results of the paper: "Worst-Case Running Times for Average-Case Algorithms" by Antunes and Fortnow, I was wondering about the existence of further results linking basic computational depth and hard/easy instances of NP-complete problems.
I mean, if a NP-complete has an exponential number of p-hard instances for any polynomial p for an algorithm A (instances that cannot be recognized in p-time) for sizes n sufficiently big, then it seems that the computational depth of such instancexs x is: BCD_p(x) = K^p(x) - K(X) should be O(1) (they are like random strings)
(Although this last observation is something I only have an informal explanation of why it should be)
So, looking at the results of Antunes and Fortnow, it seems that for any polynomial p there would exist instances x such that the running time with A: T_A(x) > p(|x|) >= 2^(BCD_p(X)+log(x)) (for instances with sufficiently big size n)
I would like to know if there are formal results related to this possible connection between p-hard instances and low basic computational depth. And there could be also connections with computational cores (sets of instances hard for any algorithm solving a problem).