ON RESOURCE-BOUNDED INSTANCE COMPLEXITY

The instance complexity of a string x with respect to a set A and time bound t, ic(t)(x : A), is the length of the shortest program for A th at runs in time t, decides x correctly, and makes no mistakes on other strings (where ''do not know'' answers are permitted). The instance c omplexity conjecture of Ko, Orponen, Schoning, and Watanabe (1986) sta tes that for every recursive set A not in P and every polynomial t the re is a polynomial t' and a constant c such that for infinitely many x , ic(t)(x: A) greater than or equal to C-t' (x) - c, where C-t'(x) is the t'-time bounded Kolmogorov complexity of x. In this paper the conj ecture is proved for all recursive tally sets and for all recursive se ts which are NP-hard under honest reductions, in particular it holds f or all natural NP-hard problems. The method of proof also yields the p olynomial-space bounded and the exponential-time bounded versions of t he conjecture in full generality. On the other hand, the conjecture it self turns out to be oracle dependent: In any relativized world where P = NP the conjecture holds, but there are also relativized worlds whe re it fails, even if C-complexity is replaced by Sipser's CD-complexit y. Additionally it is proved that the instance complexity measure is n oncomputable and it is investigated whether for every polynomial t the re is a polynomial t' such that C-t'-complexity is bounded above by CD t-complexity.