Anzeige
Erschienen in:
2012 | OriginalPaper | Buchkapitel
Komplexitätstheorie
verfasst von : Prof. Dr. Markus Nebel
Erschienen in: Entwurf und Analyse von Algorithmen
Verlag: Vieweg+Teubner Verlag
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
Bisher haben wir uns ausschließlich mit Problemen beschäftigt, für die eine algorithmische Lösung existierte, die mit einer in der Eingabegröße polynomiellen Laufzeit auskommt. Doch was ist, wenn wir eine solche Lösung nicht finden?Wie sollen wir diesen Umstand unserem Auftraggeber erklären?Wenn wir ihm beweisen könnten, dass nicht nur wir keinen solchen Algorithmus finden, sondern dass für das betrachtete Problem kein Algorithmus mit polynomieller Laufzeit existiert, kann er wohl kaum mit uns unzufrieden sein. Er sollte dann vielmehr sein Problem neu formulieren (vielleicht ist er ja nur an Spezialfällen interessiert, für die effiziente Lösungen existieren) oder sich mit approximativen Lösungen zufriedengeben (hierzu kommen wir im nächsten Kapitel).