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).

  • $\begingroup$ I have found now a reference: "Kolmogorov complexity cores", by André Souto, that it may provide some answers to my question. $\endgroup$ – Ramon Bejar Torres Jul 28 '16 at 18:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.