Anzeige
Erschienen in:
1986 | ReviewPaper | Buchkapitel
What is a hard instance of a computational problem?
verfasst von : Ker-I Ko, Pekka Orponen, Uwe Schöning, Osamu Watanabe
Erschienen in: Structure in Complexity Theory
Verlag: Springer Berlin Heidelberg
Enthalten in: Professional Book Archive
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
In this paper a measure for the complexity of particular instances with respect to a given decision problem is introduced and investigated. Intuitively, an instance x is considered to be hard for a problem A if every algorithm that decides A and runs "fast" on x needs to look up (a description of) x in a table. A main result states that all problems not in P have infinitely many (polynomially) hard instances. Further, there exist problems in EXPTIME with all their instances being hard. The behavior of hard instances under polynomial reductions and the connections with complexity cores and circuits are studied.