On the instance complexity of NP-hard problems
Pekka Orponen · 2002
The t-bounded instance complexity of a string x with respect to a set A, ic/sup t/(x:A), is defined as the size of the smallest program (roughly, Turing machine) that runs in time t, decides x correctly, and makes no mistakes on other strings (don't know answers are permitted). For certain conditions on A, it is proved that if P not=NP, then for any polynomial t and constant c, ic/sup t/(x:A)>c log mod x mod i.o.; and if EXPTIME not=NEXPTIME, then for any polynomial t there exists a polynomial t' and a constant c such that ic/sup t/(x:A)>K/sup t/'(x)-c i.o.>