1987 | OriginalPaper | Buchkapitel
Average Case Complete Problems
verfasst von : Leonid A. Levin
Erschienen in: Open Problems in Communication and Computation
Verlag: Springer New York
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
Many interesting combinatorial problems were found to be NP-complete. Since there is little hope to solve them fast in the worst case, researchers look for algorithms which are fast just “on average,” This matter is sensitive to the choice of a particular NP-complete problem and a probability distribution of its instances. Some of these tasks are easy and some not. But one needs a way to distinguish the “difficult on average” problems. Such negative results could not only save “positive” efforts but may also be used in areas (like cryptography) where hardness of some problems is a frequent assumption. It is shown in [1] that the Tiling problem with uniform distribution of instances has no polynominal “on average” algorithm, unless every NP-problem with every simple probability distribution has it.