Format:
1 Online-Ressource (312S.)
ISBN:
9783322800244
,
9783519003151
Series Statement:
TEUBNER-TEXTE zur Informatik 32
Note:
Das vorliegende Buch ist aus langjährigen Vorlesungen entstanden, die ich mit häufig wechselnden Inhalten an den Universitäten Jena, Greifswald, Pisa und Mailand gehalten habe. Es ist als eine Einführung in die Komplexitätstheorie gedacht, die auch für Nichttheoretiker noch lesbar ist. Gleichzeitig führt es auf ausgewählten Gebieten an den aktuellen Forschungsstand heran. Die Komplexitätstheorie ist inzwischen so umfangreich geworden, daß es nicht möglich und auch gar nicht mehr wünschenswert ist, sie in ihrer Gesamtheit darzustellen. Sie hat sich seit den 60er Jahren durch die Frage nach der Qualität von Berechnungen aus der Berechnungstheorie heraus entwickelt, die ihrerseits als die elementare Grundlage der Rekursionstheorie aufgefaßt werden kann. Insofern ist die Komplexitätstheorie von Haus aus strukturell in dem Sinne, daß Begriffe und Methoden aus der Rekursionstheorie in natürlicher Weise auch hier fruchtbar werden, und ich verzichte deshalb darauf, von struktureller Komplexitätstheorie zu sprechen. Typische Beispiele sind die verschiedenen komplexitätsbeschrankten Reduzierungen mit den zugehörigen Vollständigkeitsbegriffen (vgl. z.B. die Hausdorffsche Hierarchie und die Polynomialzeithierarchie), ohne die die Komplexitätstheorie nicht vorstellbar wäre. Einer der zentralen Leitbegriffe für dieses Buch ist der Begriff der Reduktion. Immer wieder werden vollständige Mengen in den verschiedenen Komplexitätsklassen identifiziert. Besondere Beachtung verdienen dabei NP-Probleme, von denen stark vermutet wird, daß sie nicht NP-vollständig sind, nämlich das Primzahl- und das Graphisomorphieproblem. Andererseits wird hier, wo eher theoretische Gesichtspunkte im Vordergrund stehen, nicht einmal ansatzweise versucht, die reiche Welt der unterschiedlichsten Arten vollständiger Probleme und ihrer approximativen Lösung zu dokumentieren
Language:
German
Keywords:
Komplexitätstheorie
DOI:
10.1007/978-3-322-80024-4
URL:
Volltext
(lizenzpflichtig)
Author information:
Wechsung, Gerd 1939-
Bookmarklink
