INSTANCE COMPLEXITY

We introduce a measure for the computational complexity of individual instances of a decision problem and study some of its properties. The instance complexity of a string x with respect to a set A and time bou nd t, ic(t)(x : A), is defined as the size of the smallest special-cas e program for A that runs in 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 in P if and only if there exist a polynomial t a nd a constant c such that ic(t)(x: A) less-than-or-equal-to c for all x; on the other hand, if A is NP-hard and P not-equal NP, then for all polynomials t and constants c, ic(t)(x:A) > c log Absolute value of x for infinitely many x. Observing that K(t)(x), the t-bounded Kolmogor ov complexity of x, is roughly an upper bound on ic(t)(x: A), we proce ed to investigate the existence of individually hard problem instances , i.e., strings whose instance complexity is close to their Kolmogorov complexity. We prove that if t(n) greater-than-or-equal-to n is a tim e-constructible function and A is a recursive set not in DTIME(t), the re then exist a constant c and infinitely many x such that ic(t)(x:A) greater-than-or-equal-to K(t)(x) - c, for some time bound t'(n) depend ent on the complexity of recognizing A. Under the stronger assumptions that the set A is NP-hard and DEXT not-equal NEXT, we prove that for any polynomial t there exist a polynomial t' and a constant c such tha t for infinitely many x, ic(t)(x:A) greater-than-or-equal-to K(t)(x) - c. If A is DEXT-hard, then the same result holds unconditionally. We also prove that there is a set A is-an-element-of DEXT such that for s ome constant c and all x, ic(exp)(x : A) greater-than-or-equal-to K(ex p)'(x) - 2 log K(exp')(x) - c, where exp(n) = 2(n) and exp'(n) = cn2(2 n) + c.