Die Komplexitätstheorie ist inzwischen eine ausgefeilte Theorie. Viele wichtige und nützliche Ergebnisse sind schwer vermittelbar, da der Weg zu Ergebnissen für konkrete Probleme lang und beschwerlich ist. Während die NP-Vollständigkeitstheorie die gesamte Informatik beeinflußt hat, werden die neueren Ergebnisse in der Ausbildung an den Rand gedrängt. Dieses Lehrbuch trifft eine Auswahl unter den Ergebnissen, so dass die Bedeutung der Komplexitätstheorie für eine moderne Informatik in den Mittelpunkt rückt.
Author(s): Ingo Wegener
Series: Springer-Lehrbuch
Edition: 1
Publisher: Springer
Year: 2003
Language: German
Pages: 332
Tags: Математика;Дискретная математика;
Cover......Page 1
Springer-Lehrbuch......Page 2
Komplexitatstheorie......Page 4
ISBN 9783540001614......Page 5
Vorwort......Page 6
Inhaltsverzeichnis......Page 8
1. Einleitung......Page 12
2. Algorithmische Probleme und ihre Komplexität......Page 24
3. Die grundlegenden Komplexitätsklassen......Page 40
4. Reduktionen - algorithmische Beziehungen
zwischen Problemen......Page 58
5. Die NP-Vollständigkeitstheorie......Page 80
6. NP-vollständige und NP-äquivalente
Probleme......Page 94
7. Die Komplexitätsanalyse von Problemen......Page 106
8. Die Komplexität von Approximationsproblemen - klassische Resultate......Page 116
9. Die Komplexität von Black-Box-Problemen......Page 133
10. Weitere Komplexitätsklassen und Beziehungen zwischen den Komplexitätsklassen......Page 146
11. Interaktive Beweise......Page 164
12. Das PCP-Theorem und die Komplexität von Approximationsproblemen......Page 180
13. Weitere klassische Themen der Komplexitätstheorie......Page 206
14. Die Komplexität von nichtuniformen Problemen......Page 224
15. Kommunikationskomplexität......Page 242
16. Die Komplexität boolescher Funktionen......Page 276
Schlussbernerkungen......Page 304
A. Anhang......Page 306
Literaturverzeichnis......Page 322
Sachverzeichnis......Page 326
