Die Komplexitätstheorie untersucht den algorithmischen Aufwand zur Lösung von Problemen mit Hilfe einer Maschine. Dabei werden Rechnermodelle wie Turing-Maschinen oder Registermaschinen verwendet, um von speziellen Architektur- und Implementationsdetails unabhängige Ergebnisse zu gewinnen. Neben den klassischen Komplexitätsmaßen Zeitaufwand und Speicherplatzbedarf werden eine Reihe weiterer Maße zur Strukturierung eingesetzt. Algorithmische Probleme werden diesbezüglich klassifiziert und in Beziehung zueinander gesetzt. Die Suche nach effizienten Lösungsstrategien wird komplementiert durch den (im allgemeinen sehr schwierigen) Nachweis unterer Schranken für den Lösungsaufwand. Komplexitätstheoretische Resultate haben auch unmittelbare Bedeutung für die Praxis erlangt, beispielsweise Ergebnisse aus dem Bereich der NP-Vollständigkeit für die Lösbarkeit von kombinatorischen Optimierungsproblemen sowie die Sicherheit von Cryptosystemen. Komplexitätstheoretische Untersuchungen verwenden sehr wesentlich Methoden aus der Diskreten Mathematik, andererseits sind dabei auch eine Reihe neuartiger mathematischer Fragestellungen aufgeworfen worden.

Keywords

Authors and Affiliations

Med. Universität zu Lübeck, Deutschland

K. Rüdiger Reischuk

Bibliographic Information

Book Title: Komplexitätstheorie Band I: Grundlagen
Book Subtitle: Maschinenmodelle, Zeit- und Platzkomplexität, Nichtdeterminismus
Authors: K. Rüdiger Reischuk
Series Title: XLeitfäden der Informatik
DOI: https://doi.org/10.1007/978-3-322-80139-5
Publisher: Vieweg+Teubner Verlag Wiesbaden
eBook Packages: Springer Book Archive
Copyright Information: Springer Fachmedien Wiesbaden 1999
Softcover ISBN: 978-3-519-12275-3Published: 01 January 1999
eBook ISBN: 978-3-322-80139-5Published: 08 March 2013
Series ISSN: 1615-5432
Edition Number: 2
Number of Pages: XII, 355
Number of Illustrations: 1 b/w illustrations
Topics: Algorithm Analysis and Problem Complexity, Theory of Computation, Computer Science, general

Publish with us

Policies and ethics

Authors:

Sections

Buy it now

Buying options

Other ways to access

Table of contents (6 chapters)

Front Matter

Das Modell der Turing-Maschine und ihre Komplexität

Weitere Maschinenmodelle

Hierarchie-Sätze

Vergleich von Speicherstrukturen

Zeit- versus Platzkomplexität

Sequentielle Komplexitätsklassen

Back Matter

About this book