Der Physik ist es in vorbildlicher Weise gelungen, ihre Erkenntnisse in die breitere Öffentlichkeit zu transportieren. Sie hatte es leicht bei explosiven Themen wie der Atomtheorie, aber selbst so Schwieriges wie Quantenphysik oder Schwarze Löcher findet sich in populärwissenschaftlichen Werken gut verständlich erklärt. Zur Informatik dagegen gibt es außer der Fachliteratur vor allem Bücher, die uns eine schöne neue Welt versprechen. Das ist nur ein Teil der Wahrheit. Wie in jeder Wissenschaft stehen Errungenschaften, die uns das Leben erleichtern, solchen von eher zweifelhaftem Wert gegenüber. Und es gibt Grenzen des Machbaren und des mit den vorhandenen Ressourcen Machbaren.

Diese Grenzen sind das Thema des Buches von David Harel vom weltberühmten Weizmann-Institut in Rehovot (Israel). Der englische Titel "Computers Ltd.: what they really can’t do" gibt sein Anliegen viel deutlicher wieder als der deutsche (insgesamt ist die Übersetzung aber gut gelungen). Was also können Rechner nicht nur "noch nicht", sondern prinzipiell nicht? Können wir derartig weit reichende Resultate auch im mathematischen Sinn beweisen? Wir können – und das ergibt ein faszinierendes Forschungsgebiet, die Komplexitätstheorie und die Berechenbarkeitstheorie.

Natürlich müssen die Fragen präzisiert werden. Könnte ein Rechner eingesetzt werden, um aus einer Gerichtsverhandlung ein Urteil zu berechnen? Schon, aber die Auswirkungen wären vermutlich schlimm. Darum geht es in diesem Buch nicht. Rechner können bisher nur schlecht Texte in eine andere Sprache übersetzen. Auch darum geht es nicht, weil wir nur schwer richtige von falschen Ergebnissen abgrenzen können.

Was bleibt dann? Sehr viel: alle Optimierungsprobleme aus den Natur- und Ingenieurwissenschaften und dem Alltag mit einem gut überprüfbaren Optimierungsziel, aber auch Fragen über die Lösbarkeit von Problemen oder die Korrektheit von Lösungsverfahren. Zudem sind wir an allgemeinen Problemen interessiert. Also nicht am kürzesten Weg von Dortmund nach Moskau, auch nicht an der kürzesten Verbindung zwischen zwei beliebigen Städten auf unserem Erdball, sondern an einem Verfahren, das zu einer Liste von beliebig, aber endlich vielen Orten und Verbindungen (mit Längenangaben) zwischen einigen Orten kürzeste Wege findet. Dies ist keine Einschränkung, da Rechnerlösungen von dieser allgemeinen Art sind.

Rechner können nicht alle von uns zugelassenen Probleme lösen, weil es viel mehr (allgemeine) Probleme als Lösungsverfahren gibt. Dies kann man beweisen, aber so geht das Buch nicht vor. Harel betrachtet stets konkrete Probleme. Er diskutiert keine mathematischen Beweise, sodass das Buch gut verständlich bleibt; stattdessen begründet er seine Behauptungen eindringlich, überzeugend und mit einer bildhaften Sprache.

Eine solche Behauptung ist: Es gibt keinen Algorithmus, der für ein beliebiges Computerprogramm, das auf Listen von Zahlen operiert, entscheidet, ob es jede Zahlenliste aufsteigend sortiert. Wohlgemerkt: Für viele Programme können wir dies nachweisen, aber nicht allgemein.

Andere Probleme sind prinzipiell lösbar, aber so schwer, dass die Ressourcen unseres Universums nicht ausreichen, sie zu lösen.

Noch faszinierender ist die Frage, die unter dem Namen "P=NP?" berühmt geworden ist. Tausende von Problemen, darunter viele der täglich zu lösenden Optimierungsprobleme, gehören zu der Problemklasse NP. Wir wissen nicht, ob sie effizient (mit realistischen Ressourcen) lösbar sind oder nicht. Wir wissen aber, dass sie alle effizient lösbar sind oder alle nicht effizient lösbar sind. Das Buch stellt anschaulich dar, wie derartige Ergebnisse erzielt werden. Die Fachwelt ist sich einig, dass auch hier die schlechte Nachricht "nicht effizient lösbar" wahr ist.

Aber sind schlechte Botschaften nur schlecht? Kryptografie, die Verschlüsselung von Daten, beruht ja gerade darauf, dass legale Nutzer einen Vorteil gegenüber illegalen haben. Moderne Kryptosysteme sind prinzipiell knackbar – nur hat niemand die dafür nötigen Ressourcen.

Das Buch ist von einem weltbekannten Experten in einem unvergleichbaren Stil geschrieben: leicht und locker und dennoch präzise. Notwendige Vereinfachungen führen nicht zu nur noch fast richtigen Aussagen. Wer abstrakte Gedanken nicht fürchtet, wird dieses Buch mit Genuss lesen und hinterher die Informatik mit anderen Augen sehen.

Eine kleine Ergänzung: David Harel wählt häufig den Test, ob eine Zahl Primzahl ist, als Beispiel. Im vergangenen Jahr haben Manindra Agrawal, Neeraj Kayal und Nitin Saxena aus Kanpur gezeigt, dass dieses Problem effizient lösbar ist – es gibt also auch gute Nachrichten.

Aus: Spektrum der Wissenschaft 11 / 2003, Seite 90
© Spektrum der Wissenschaft Verlagsgesellschaft mbH