Inhalt: Ingrid Biehl, Copyright-Schutz digitaler Daten durch kryptographische Fingerprinting-Schemata: Kryptographische Zeichen – Die Fingerprinting-Modelle – Ein assymetrisches Fingerprinting-Schema – Ein anonymes Fingerprinting-Schema Michael Thielscher, Kognitive Robotik – Perspektiven und Grenzen der KI-Forschung: Ein neuartiges Werkzeug – Kognitive Fähigkeiten bei Robotern – Perspektiven und Grenzen der „künstlichen Intelligenz“-Forschung
Die klassische Komplexitätstheorie untersucht die Schwierigkeit von Probleminstanzen im schlimmsten Fall. In der Praxis zeigt sich jedoch oft, dass solche Probleme schnell gelöst werden können, was die Wahrscheinlichkeit schwieriger Instanzen in Anwendungen verringert. Daher ist es wichtig, die durchschnittliche Komplexität zu betrachten, insbesondere die mittlere Laufzeit optimaler Lösungsalgorithmen, wenn die Eingaben einer Wahrscheinlichkeitsverteilung folgen. Die average-case Komplexitätstheorie konzentriert sich nicht auf spezifische Probleme oder Verteilungen, sondern auf allgemeine Zusammenhänge, ähnlich der worst-case Komplexitätstheorie. Ein zentrales Thema ist die Frage, ob es auch im Durchschnittsfall Probleme gibt, die NP-vollständig sind. Das Buch entwickelt einen allgemeinen Rahmen für diese Theorie und leitet mehrere grundlegende Ergebnisse innerhalb dieses Rahmens ab. Die Inhalte umfassen eine Einführung, starke und schwache average-case Modelle, Klassen von Dichten und Sprachklassen sowie Aspekte der Komplexitäts- und Vollständigkeitstheorie.