Instance complexity

We introduce a measure for the computational complexity of individual instances of a decision problern and study some of its properties. The inntance complexity of a string x with respect to a set A and time bound t, ic t(x : A), is defined as the size of the smallest special-case program for A that runs in time t, decides x correctly, and makes no mistakes on other strings ("don´t know" answers are permitted).