On hard instances

✍ Scribed by Martin Mundhenk

• Book ID: 104326612
• Publisher: Elsevier Science
• Year: 2000
• Tongue: English
• Weight: 107 KB
• Volume: 242
• Category: Article
• ISSN: 0304-3975
• DOI: 10.1016/s0304-3975(98)00262-x

✦ Synopsis

Instance complexity was introduced by Orponen, Ko, Sch oning, and Watanabe (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 proved that NP-hard sets have p-hard instances, unless P = NP. The unbounded version of the conjecture was proven wrong by .

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 (1975) Nevertheless, NP-hard sets must have super-polynomially dense hard instances, unless P = NP.