Komplexitätstheorie Band I: Grundlagen: Maschinenmodelle, Zeit- und Plazkomplexität, Nichtdeterminismus

نظریه پیچیدگی تلاش الگوریتمی برای حل مسائل با کمک یک ماشین را بررسی می کند. مدل‌های کامپیوتری مانند ماشین‌های تورینگ یا ماشین‌های ثبت برای به دست آوردن نتایج مستقل از معماری خاص و جزئیات پیاده‌سازی استفاده می‌شوند. علاوه بر معیارهای کلاسیک پیچیدگی زمان و حافظه مورد نیاز، تعدادی معیار دیگر برای ساختاربندی استفاده می شود. مسائل الگوریتمی از این نظر طبقه بندی شده و به یکدیگر مرتبط هستند. جستجو برای استراتژی های راه حل کارآمد با اثبات (به طور کلی بسیار دشوار) از حد پایین تر برای تلاش راه حل تکمیل می شود. نتایج نظری پیچیدگی نیز اهمیت مستقیمی برای عمل به دست آورده اند، به عنوان مثال نتایج حاصل از حوزه کامل بودن NP برای حل مشکلات بهینه سازی ترکیبی و امنیت سیستم های رمزنگاری. تحقیقات مبتنی بر نظریه پیچیدگی تا حد زیادی از روش‌های ریاضیات گسسته استفاده می‌کنند، اما از سوی دیگر تعدادی سؤال ریاضی جدید مطرح شده است.

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.