Theoretical Computer Science 242(1-2), pp.301-311, July 2000.
Preliminary version appeared under the titel
NP-hard sets have many hard instances
at Proc. 25th Mathematical Foundations of Computer Science,
Lecture Notes in Computer Science, #1295:428-437,
Springer Verlag, 1997.
Instance complexity was introduced by Orponen, Ko, Schöning, and Watanabe (JACM 1994) as a measure of the complexity of individual instances of a decision problem. Comparing instance complexity to Kolmogorov complexity, they introduced the notion of p-hard instances, and conjectured that every set not in P has p-hard instances. Whereas this conjecture is still unsettled, Fortnow and Kummer (TCS 1995) proved that NP-hard sets have p-hard instances, unless P=NP. The unbounded version of the conjecture was proven wrong by Kummer (Structures 1995)
We introduce a slightly weaker notion of hard instances. In the unbounded version, we characterize the classes of recursive enumerable resp. recursive sets by hard instances. In bounded versions, we characterize the class P. Hard instances are shown to be stronger than complexity cores (introduced by Lynch (JACM 1975)). Nevertheless, NP-hard sets must have super-polynomially dense hard instances and cannot consist of hard instances only, unless P=NP.
Back to my homepage