Complexity theory. Limits of the efficiency of algorithms
type: Item
instance of: scholarly article
title: Complexity theory. Limits of the efficiency of algorithms
zbMATH Open document ID: 1055.68057
author: Ingo Wegener
published in: Springer-Lehrbuch
publication date: 2003-07-02T00:00:00Z
review text: 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 ande…
reviewed by: Hans-Dietrich Hecker
Mathematics Subject Classification ID: 68Q15
Mathematics Subject Classification ID: 68-01
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 1945069
zbMATH Keywords: complexity classes
zbMATH Keywords: approximation algorithms
zbMATH Keywords: theory of computing
zbMATH Keywords: randomized algorithms
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 1945069