2005 | OriginalPaper | Buchkapitel
Die NP-Vollständigkeitstheorie
verfasst von : Prof. Dr. Ingo Wegener
Erschienen in: Theoretische Informatik
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
Wann ist die Aufgabe, einen effizienten Algorithmus für ein bestimmtes Problem zu finden, erfolgreich gelöst? Polynomielle Algorithmen für Registermaschinen gelten als effiziente Algorithmen. Nach den Ergebnissen aus Kapitel 2 können wir hierbei Registermaschinen durch Turingmaschinen, aber auch durch C++-Programme oder Java-Programme ersetzen.