Complexity theory. Limits of the efficiency of algorithms (Q1395898)

Der Autor legt mit diesem Buch ein weiteres interessantes Buch zur Komplexität von Algorithmen vor. Dabei wird von vornherein die Zielstellung verfolgt, nicht ein Werk vorzulegen, das primär die neuesten Ergebnisse der Forschung zu diesem Gebiet präsentiert. Nach einer überzeugenden Argumentation, dass die Komplexitätstheorie ein Kerngebiet der modernen Informatik ist, wurde das Buch unter dem Gesichtspunkt entworfen, ein Lehrbuch zu schreiben, das sich an alle Studenten richtet, die Informatik als Berufsziel gewählt haben. Die oft übliche Vorgehensweise, das Konzept des Nichtdeterminismus im Zusammenhang mit ``Ratestrategien'' zu entwickeln, wird durch die Einführung randomisierter Algorithmen ersetzt. Es ist sicher auch Geschmackssache, welchem Weg man hier den Vorzug gibt; ich finde die Herangehensweise interessant. Sie hat auf jeden Fall den Vorteil, dass das besonders aktuelle und praktisch wichtige Gebiet der randomisierten Algorithmen dem Lernenden so frühzeitig wie möglich nahe gebracht wird. Das Buch bleibt mit seinen Inhalten im Wesentlichen im üblichen Rahmen. Hervorheben möchte ich die Kapitel 11 und 12, die sich mit der Komplexität von Ap\-pro\-xi\-ma\-tionsproblemen beschäftigen, wobei das PCP-Theorem naturgemäß im Mittelpunkt der Überlegungen steht. Folgende Themen werden unter anderem noch behandelt: Kom\-ple\-xi\-täts\-klas\-sen, Reduktionen, NP-Vollständigkeitstheorie, Komplexitätsanalyse von Problemen, klassische Resultate bei Approximationsproblemen, Black-Box-Probleme, Beziehungen zwischen Komplexitätsklassen und weitere klassische Themen der Komplexitätstheorie (wie P-SPACE-vollständige Probleme und die auch für parallele Algorithmen wichtigen Komplexitätsklassen innerhalb P). Es folgen Untersuchungen über die Komplexität Boolescher Funktionen, denen offenbar auch das spezielle Interesse des Autors gilt. Das Literaturverzeichnis ist angemessen. Die interessante Internetadresse des Autors gibt einen Hinweis auf gefundene Druckfehler und auf andere teils vergriffene Bücher des Autors. Sein neues Buch ist wieder sehr gut lesbar und sicher ein Gewinn für alle Informatiker und die, die es werden wollen.