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 that runs in time t, decides x correctly, and makes no mistakes on other strings (where “do not know” answers are permitted). The instance complexity conjecture of Ko, Orponen, Schöning, and Watanabe (1986) states that for every recursive set A not in P and every polynomial t there is a polynomial t′ and a constant c such that for infinitely many x, ic t (x: A) ⩾ C t′ (x) − c, where C t′ (x) is the t′-time bounded Kolmogorov complexity of x. In this paper the conjecture is proved for all recursive tally sets and for all recursive sets which are NP-hard under honest reductions, in particular it holds for all natural NP-hard problems. The method of proof also yields the polynomialspace bounded and the exponential-time bounded versions of the conjecture in full generality. On the other hand, the conjecture itself turns out to be oracle dependent: In any relativized world where P = NP the conjecture holds, but there are also relativized worlds where it fails, even if C-complexity is replaced by Sipser's CD-complexity. Additionally it is proved that the instance complexity measure is noncomputable and it is investigated whether for every polynomial t there is a polynomial t′ such that C t′-complexity is bounded above by CDt -complexity.

Authors

• Lance Fortnow
• Martin Kummer

Keywords

No keywords are indexed for this paper.