Random Strings Make Hard Instances

摘要

We establish the truth of the “instance complexity conjecture” in the case of DEXT-complete sets over polynomial time computations, and r.e. complete sets over recursive computations. Specifically, we obtain for every DEXT-complete setAan exponentially dense subsetCand a constantksuch that for every nondecreasing polynomialt(n)=Ω(nk), ict(x:A)⩾Kt(x)−cholds for some constantcand allx∈C, where ictandKtare thet-bounded instance complexity and Kolmogorov complexity measures, respectively. For any r.e. complete setAwe obtain an infinite setC⊆Āsuch that ic(x:A)⩾K(x)−cholds for some constantcand allx∈C, where ic andKdenote the time-unbounded versions of instance and Kolmogorov complexities, respectively. The proofs are based on the observation thatKolmogorov random stringsare individually hard to recognize by bounded computations.