RANDOM STRINGS MAKE HARD INSTANCES

We establish the truth of the ''instance complexity conjecture'' in th e case of DEXT-complete sets over polynomial time computations, and r. e. complete sets over recursive computations. Specifically, we obtain for every DEXT-complete set A an exponentially dense subset C and a co nstant k such that for every nondecreasing polynomial t(n) = Omega(n(k )), ic(t)(x: A) greater than or equal to K-t(x)-c holds for some const ant c and all x is an element of C, where ic(t) and K-t are the t-boun ded instance complexity and Kolmogorov complexity measures, respective ly. For any r.e. complete set A we obtain an infinite set C subset of or equal to (A) over bar such that ic(ix: A) greater than or equal to K(x)-c holds for some constant c and all x is an element of C, where i c and K denote the time-unbounded versions of instance and Kolmogorov complexities, respectively. The proofs are based on the observation th at Kolmogorov random strings are individually hard to recognize by bou nded computations. (C) 1996 Academic Press, Inc.