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.