Instance complexity
Pekka Orponen, Ker‐I Ko, Uwe Schöning, Osamu Watanabe · Journal of the ACM · 1994
We introduce a measure for the computational complexity of mdiwdual instances of a decision problem and study some of Its properties.The instance complexity of a string ~with respect to a set A and time bound t, ict(x : A). is defined as the size of the smallest special-case program for A that run> m time t,decides x correctly, and makes no mistakes on other strings ("don't know" answers are permitted).We prove that a set A is m P if and only if there exist a polynomial t and a constant c such that ic'(x : A) c log I ~I for ]nfimtely many x.Obserwng that Kf(x), the t-bounded Kolmogorov complexity of x, N roughly an upper bound on ]Ct(.t: A), we proceed to investigate the existence of mdiwdually hard problem Instances.].e , strings whose instance complexity E close to their Kolmogorov complexity.We prove that if t(n) z n is a time-constructible function and A 1s a recurswe set not in DTIME(t), there then exist a constant c and mfimtely many I such that ic'(x : ,4) z K' (x) -c. for some Prehmmary versions of parts of this work have appeared under the titles "What 1s a hard instance of a computational problem?" m Proceedings of tize Conference on Structare m Cornplexm Theory (Berkeley, Calif., June i 986), and "On the instance complexity of NP-hard problems" in Procecduzgs of the 5tk .4nrrualConference on StntctLwe m Cowrpkwty Theory (Barcelona, Spain, July 1990).