Schneller als jede andere Disziplin hat sich in den letzten 25 Jahren die Informatik entwickelt – und dabei eine Fülle theoretischer Fragen aufgeworfen. Wie immer in solchen Situationen musste man feststellen, dass zu ihrer Bewältigung die verfügbare Mathematik nicht ausreicht, sondern neue Forschungsgebiete zu erkunden sind. So entwickelte sich ein bemerkenswerter Schwung neuer Ideen.

Alles begann in den 1930er Jahren, als Alan Turing, Kurt Gödel und Alonzo Church theoretisch abklärten, was Computer, die es damals noch gar nicht gab, würden berechnen können – und was nicht. Aber erst im letzten Vierteljahrhundert ist der Mathematik ein kraftvoller neuer Zweig gewachsen. Neben die klassische Theorie des Kontinuums trat die Mathematik des Diskreten, der Berechnung und der Information. Auf dem Humus der elektronischen Schaltkreise wuchs ein blühender Garten, von dem wir bis jetzt allenfalls ein paar Hauptwege kennen.

Wie bringt man einen Computer dazu, das zu tun, was man will? Man schreibt ihm eine Liste eindeutiger Anweisungen, die möglicherweise mehrfach auszuführen sind: einen "Algorithmus". Das klassische, mehr als 2000 Jahre alte Beispiel ist der Euklid’sche Algorithmus, der den größten gemeinsamen Teiler zweier natürlicher Zahlen bestimmt. Theoretisch ist die Zahl der auszuführenden Anweisungen nicht begrenzt; in der Praxis dachte zu Zeiten des mühsamen Handrechnens niemand ernsthaft daran, mehr als allenfalls einige hundert elementare Rechenoperationen zu vollführen. Maschinen, die Millionen, später Milliarden von Rechenschritten fehlerfrei bewältigen, sind etwas qualitativ Neues und erfordern eine neue, in ihrem Kern mathematische Wissenschaft, die Algorithmentheorie.

Die Programmierung von Computern ist weder einfach noch nahe liegend. Eine Methode, die auf dem Papier ganz vernünftig aussieht, kann im Reich der Rechner vollkommen verfehlt sein. So gibt es für die Lösung eines linearen Gleichungssystems eine elegante, geschlossene Formel, die Cramer’sche Regel. Aber sie erfordert wesentlich höheren Rechenaufwand als andere Methoden und ist für Systeme mit mehr als zwanzig Gleichungen praktisch unbrauchbar. Die Kunst besteht darin, Algorithmen zu ersinnen, die eine vorgegebene Aufgabe in möglichst kurzer Zeit bewältigen. Im Gegensatz zu der naiven Vorstellung vom Supercomputer erübrigt die Leistungsfähigkeit der Maschine nicht das eigene Denken. Im Gegenteil: Je leistungsfähiger eine Maschine ist, umso mehr (mathematische) Vorarbeit ist erforderlich, um sie richtig einzusetzen.

Hochgeschwindigkeitsberechnung

Das gilt bereits für eine so alltägliche Aufgabe wie die Multiplikation zweier natürlicher Zahlen – wenn diese Tausende oder Millionen von Ziffern haben. In den 1970er Jahren entwickelte man ein Verfahren, zwei n-stellige Zahlen in einer Zeit miteinander zu multiplizieren, die proportional zu nlog(n)log(log(n)) ist. (Dabei bezeichnet log den natürlichen Logarithmus.) Praktisch ist diese Rechenzeit so gut wie proportional zu n und damit viel kürzer als diejenige des klassischen Verfahrens, das im Wesentlichen gleich der uralten Schulmethode ist und eine Rechenzeit proportional zu n² erfordert.

Ein interessantes Anwendungsgebiet von Algorithmen ist die Berechnung mathematischer Konstanten wie , e oder —2. Dank der jüngsten Fortschritte sind die wichtigsten unter ihnen inzwischen auf mehrere Milliarden Stellen hinter dem Komma bekannt. Gelegentlich gibt es dabei Überraschungen, wie eine neue Formel zur Berechnung von . Bis vor kurzem war die berühmte Kreiszahl wie ein Buch, das man Seite für Seite lesen musste: Eine Ziffer dieser Zahl konnte man nur ermitteln, wenn man alle vorangehenden Ziffern schon bestimmt hatte. Im Jahr 1995 gelang es einer kanadischen Forschergruppe, diesen Zwang zu durchbrechen: Jonathan und Peter Borwein sowie Simon Plouffe entdeckten eine neue Formel, mit der man die Ziffern der Binärdarstellung von unabhängig voneinander berechnen kann (Spektrum der Wissenschaft 5/1997, S. 10). Mithilfe dieser Formel ermittelte Colin Percival fünf Jahre später die 10¹⁵-te Binärstelle von und noch einige in deren Nachbarschaft – eine Leistung, die jahrhundertelang als unmöglich gegolten hatte.

Ein weiterer Erfolg der modernen Algorithmentheorie ist die Entdeckung sehr großer Primzahlen: 1999 fand man eine Primzahl mit mehr als 2 Millionen Ziffern, 2001 eine mit 4 Millionen. In diesem Zusammenhang war die Entdeckung probabilistischer Primzahltests in den 1970er Jahren eine Überraschung. Solche Tests sagen aus, ob eine gegebene Zahl eine Primzahl ist – aber nicht mit Gewissheit, sondern mit einer sehr kleinen Irrtumswahrscheinlichkeit (Spektrum der Wissenschaft 2/1983, S. 80). Mittlerweile hat, dank leistungsfähiger Computer, die ehedem sehr esoterische Wissenschaft von den Primzahlen handfeste Anwendung gefunden: in der Kryptographie (Spektrum Dossier 4/2001 "Kryptographie").

Die Kunst des Schnellrechnens

In den letzten 25 Jahren hat sich die Algorithmentheorie weit über die Einzelfall-Fragestellungen der Informatik hinaus zu einer gewissen Reife entwickelt. Dabei hat sie tief liegende Verbindungen zur Mathematik geknüpft und unsere Sichtweisen stellenweise radikal verändert. In den Buchhandlungen erschienen Arithmetiklehrbücher einer neuen Art, die zu jedem neuen Begriff ein algorithmisches Werkzeug zum effizienten Umgang mit diesem Begriff auf dem Computer bereitstellen.

Man muss Mathematik investieren, um den Computer zu beherrschen, aber der Computer gibt der Mathematik auch etwas zurück. Er eröffnet neue Sichtweisen auf abstrakte Objekte, die eine (geeignet instruierte) Maschine besser zu handhaben versteht als der menschliche Geist – in jedem Falle mit unvergleichlich größerer Sicherheit und Genauigkeit.

Die Fortschritte der Algorithmentheorie strahlen nicht nur auf die Arithmetik, sondern auf einen wesentlichen Teil der Mathematik insgesamt aus. Die Computeralgebra, bei der die Maschine nicht nur Zahlen, sondern auch Symbole, Funktionen, Gleichungen, Matrizen und so weiter miteinander verknüpft, hat sich in den letzten 25 Jahren beachtlich entwickelt (Spektrum der Wissenschaft 3/1996, S. 88). Über Taschenrechner, die Symbole manipulieren können, und die zugehörige Software hat sie ihren Platz in den Gymnasien und Ingenieurbüros gefunden. Auch hier führt der Einbruch des Computers in die Welt der abstrakten Objekte zu einer neuen Art der angewandten Mathematik.

Über ihren belebenden Einfluss auf alte Forschungsgebiete hinaus haben die Algorithmen neue Anwendungsgebiete aufgetan. Als Beispiel sei die Rekonstruktion von Stammbäumen genannt. Früher bearbeitete man die morphologischen oder molekularen Daten von Hand – mit Methoden, die unvermeidlich in ihrer Komplexität beschränkt waren. Durch den Computer sind nicht nur umfangreichere Datenmengen, sondern auch komplexere und leistungsfähigere Verfahren in den Bereich des Machbaren gerückt. Diese ihrerseits sind unter anderem von der Graphentheorie und der Statistik inspiriert.

Ganz allgemein ist aus der Verarbeitung von Daten der Molekularbiologie ein neues, halb theoretisches, halb angewandtes Fachgebiet hervorgegangen: die Bioinformatik. Sie gewinnt immer mehr an Bedeutung und wird vielleicht die Biologie ebenso auf mathematische Füße stellen, wie es vor langer Zeit der Physik ergangen ist.

Logik, die Mutter der Informatik

Das Fundament, auf dem die so stürmisch voranschreitende Algorithmentheorie ruht, ist schon sehr alt: die mathematische Logik. Gleichwohl ist auch sie in Bewegung geraten und hat vor allem unsere Ansichten über das Programmieren nachhaltig beeinflusst. Zu Beginn der 1970er Jahre wurde die Idee der deklarativen Programmierung formuliert: Der Mensch muss nur noch sein Problem beschreiben; die Maschine übernimmt es dann, es zu lösen. Das wäre eine ungeheure Arbeitserleichterung, aber natürlich sind die Grenzen dieser Utopie offensichtlich: Wenn es zu einem Problem mehr als einen Algorithmus gibt, wie soll dann die Maschine entscheiden? Immerhin: Die Programmiersprache PROLOG, die Alain Colmerauer und seine Kollegen 1973 in Marseille implementierten, ist ein erfolgreicher Kompromiss zwischen dem Wünschenswerten und dem Machbaren. PROLOG beruht auf den Techniken des automatischen Beweisens: Die Maschine leitet aus Formeln, die als Axiome akzeptiert sind, Folgerungen ab. Die dafür entwickelten Ideen sind verallgemeinert worden und spielen in der künstlichen Intelligenz und bei den Expertensystemen eine wichtige Rolle.

Ebenfalls der mathematischen Logik entsprungen ist die Idee vom beweisbar korrekten Programm. Man gibt der Maschine einen in Symbolen der Logik geschriebenen Beweis eines Satzes, zum Beispiel: Zu jeder Zahlenfolge T gibt es eine Folge S, die dieselben Elemente wie T enthält, aber nach aufsteigender Größe sortiert. Aus diesem Beweis macht die Maschine ein Programm, von dem man sicher sein kann, dass es keinen Fehler enthält. In unserem Beispiel ordnet das Programm die Elemente der Folge T der Größe nach, was die Folge S ergibt. Dieser viel versprechende Ansatz zur Erzeugung fehlerfreier Software hat schon mehrere Erfolge bei der Verifikation von Programmen und Mikrochips erzielt.

In der Forschung zur künstlichen Intelligenz spielen neue Varianten der Logik eine wichtige Rolle. Diese "nicht-klassischen" Logiken zielen darauf ab, das menschliche Denken zu modellieren, das komplexer ist als das mathematische. So können die parakonsistenten Logiken Daten mit Widersprüchen verarbeiten. Die nichtmonotonen Logiken berücksichtigen, dass eine abgeleitete Aussage durch zusätzliche Informationen widerlegt werden kann. Weiter gibt es die Fuzzy Logic (Spektrum der Wissenschaft 3/1993, S. 90), die partielle Logik, die Modallogik und die mehrwertigen Logiken, die außer "wahr" und "falsch" noch andere Wahrheitswerte kennen.

Allgemein lehrt uns die mathematische Logik, dass die Programmierung von Computern unter allen möglichen Gesichtspunkten angegangen werden sollte – und dass große Abstraktheit kein Makel ist. Ein guter Algorithmus ist zunächst nichts weiter als eine Idee; dennoch kann er bis zu einem nützlichen Produkt weiterentwickelt werden.

Die kryptographische Welle

Ein spezielles Teilgebiet der theoretischen Informatik erlebte in den letzten 25 Jahren eine noch größere Revolution als alle anderen. Die frühere militärische Geheimwissenschaft ist zu einer zivilen Angelegenheit geworden, die anlässlich ihrer alljährlichen Kongresse eine stattliche Gemeinschaft von Wissenschaftlern versammelt: die Kryptographie.

Auslöser war die Entdeckung der Kryptographie mit veröffentlichtem Schlüssel (public key cryptography) Anfang der 1970er Jahre. Der Klartext wird mithilfe eines allgemein bekannten Schlüssels chiffriert; dagegen erfordert die Entschlüsselung die Kenntnis eines geheimen Schlüssels, der zwar durch den öffentlichen Schlüssel eindeutig bestimmt, aber nicht ohne übermäßigen Aufwand aus diesem herzuleiten ist (Spektrum der Wissenschaft 10/1979, S. 92). Die fortgeschrittenste Ausgestaltung des Prinzips ist das RSA-Verfahren, benannt nach Ronald Rivest, Adi Shamir und Leonard Adleman, die es 1977 entdeckten. (Inzwischen weiß man, dass Clifford Cocks und seine Kollegen dasselbe Verfahren schon 1973 gefunden hatten, aber nicht darüber sprechen durften.)

Mithilfe dieser Verfahren kann man, ohne vorher geheime Schlüssel auszutauschen, sicher mit einem Partner kommunizieren, dessen Identität überprüfen und eine Nachricht unfälschbar als die eigene kennzeichnen (die "elektronische Unterschrift"). Weitere Forschungen im Bereich der Kryptographie haben zur Entwicklung von effizienten und sicheren Pseudo-Zufallsgeneratoren geführt, was die Übermittlung geheimer Nachrichten mit einfachem Schlüssel (derselbe für Ver- und Entschlüsselung) sehr erleichtert (Spektrum der Wissenschaft 6/1999, S. 26).

Diese Entdeckungen zeigen einen wundervollen Weg von der abstraktesten Theorie zur konkretesten Praxis. Lange Zeit galt die Zahlentheorie als brotlose Kunst; nun findet sie eine unentbehrliche Anwendung in der Welt des Geldes. Die theoretische Informatik ist nicht etwa eine kostspielige und unnütze Spielerei zur Befriedigung des Intellekts. Vielmehr wäre unsere Welt ohne sie nicht das, was sie ist. Unsere Scheckkarte mit Chip ebenso wie die gesicherte Zahlung über das Internet beruhen auf hochabstrakter Mathematik.

Noch bleiben Fragen offen. Die Sicherheit vieler kryptographischer Algorithmen beruht darauf, dass bestimmte Probleme als "schwer" gelten (in einem unten zu präzisierenden Sinn). So beruht beispielsweise die Sicherheit von RSA darauf, dass die Faktorisierung großer Zahlen schwer ist. Das bezweifelt zwar niemand ernsthaft, aber bewiesen ist es nicht. Die Sicherheit vieler kryptographischen Methoden hängt also, entgegen mancher öffentlichen Bekundung, von einer unbewiesenen mathematischen Behauptung ab.

Fragen dieser Art gehören zu dem viel umfangreicheren Problemkreis, der den Kern der theoretischen Informatik ausmacht: zur Theorie der Berechenbarkeit. Diese ist in den 1930er Jahren entstanden und hat vor allem negative Resultate zu bieten: So ist es beispielsweise unmöglich, ein Programm zu schreiben, das unter verschiedenen Programmen diejenigen auswählt, die dieselbe Funktion berechnen. Unmöglichkeitsbeweise dieser Art haben in den letzten 25 Jahren die Grenze zwischen dem algorithmisch Berechenbaren und dem Nichtberechenbaren genauer abgesteckt.

Diese seit dreißig Jahren ständig weitergeführten Forschungen ebneten den Weg zu neuen, detaillierten Fragen der folgenden Art: Kann man eine n-stellige Zahl in polynomialer Zeit (das heißt, die Rechenzeit ist proportional einer Potenz von n) faktorisieren? Die Probleme, die in polynomialer Rechenzeit gelöst werden können, bilden die Komplexitätsklasse P. Ein Problem aus P ist also nicht nur lösbar, sondern sogar effizient (das heißt in polynomialer Zeit) lösbar. "Schwer" wird als das Gegenteil von "effizient lösbar" definiert.

Wenn allerdings eine Faktorisierung einer n-stelligen Zahl vorgelegt wird, lässt sich in polynomialer Zeit überprüfen, ob diese korrekt ist. Die Probleme, deren Lösungen sich in polynomialer Zeit verifizieren lassen, bilden die Klasse NP. Es ist heute bekannt, dass das Problem der Faktorisierung zur Klasse NP gehört. Dass es nicht zur Klasse P gehört, wird vermutet, ist aber bislang nicht bewiesen.

Dieser Mangel an Gewissheit ist sehr unangenehm, denn er betrifft einen zentralen Punkt der Komplexitätstheorie. So lange diese Frage nicht geklärt ist, kommen Bemühungen, die Sicherheit der gängigsten Methoden zu beweisen, nicht voran.

Dennoch war die Arbeit der letzten 25 Jahre nicht vergeblich. So konnte eine große Zahl neuer Schwierigkeitsklassen identifiziert werden. Sie bilden ein detailliertes Panorama, das uns hoffentlich den Weg zu der heiß ersehnten Lösung weisen wird.

Die Geburt der Quanteninformatik

Die wahre Theorie unserer physikalischen Welt ist nicht die klassische Mechanik, sondern die Quantenmechanik. Wenn wir eines Tages fähig sein sollten, zahlreiche Quantenzustände unabhängig voneinander zu präparieren und sie ungestört miteinander wechselwirken zu lassen, dann könnten wir einen Quantencomputer bauen. Seine Bauteile befinden sich nicht mehr in einem von zwei eindeutig bestimmten Zuständen ("0" und "1" wie in einem klassischen Computer), sondern in einer quantenmechanischen Überlagerung dieser beiden Zustände (Spektrum der Wissenschaft 12/1995, S. 62). Auf die theoretische Informatik, die bislang stillschweigend von einer klassischen (newtonschen) Physik ausging, kommen damit etliche Neuigkeiten zu.

So gibt es in der Kryptographie Verfahren für den geheimen Nachrichtenaustausch, deren Sicherheit nicht mehr auf unbewiesenen Vermutungen beruht, sondern auf den Grundannahmen der Quantenmechanik. Diese Protokolle verwenden polarisierte Photonen und wurden in den letzten Jahren konkret realisiert (Spektrum der Wissenschaft 1/2002, S. 86).

Das zweite Resultat wurde 1994 von Peter Shor entdeckt. Er bewies, dass ein Quantencomputer – im Gegensatz zu einem klassischen – in der Lage ist, natürliche Zahlen in polynomialer Zeit zu faktorisieren. Mit dem Quantencomputer wird also bislang Nichtberechenbares berechenbar; zu den Klassen P und NP kommen folglich neue quantenmechanische Komplexitätsklassen hinzu. Obendrein würde die Realisierung von Quantencomputern, die heute noch in weiter Ferne liegt, schwer wiegende Umwälzungen für die Kryptographie mit sich bringen.

In der Tat kommt aus der Quantenmechanik eine neue Sichtweise der Informatik und der Berechnung; bislang als absolut gültig betrachtete Modelle werden in Frage gestellt. Alle Computer der Gegenwart sind theoretisch äquivalent der klassischen Turing-Maschine, die alle Arten von Berechnungen mit Bits ausführen kann – aber nur mit klassischen Bits. Die klassische Turing-Maschine muss der Quanten-Turing-Maschine Platz machen.

---

Fortschritte der Algorithmentheorie

In einigen Bereichen wurde in den letzten Jahren besonders intensiv geforscht (in Klammern Verweis auf einen Artikel zum jeweiligen Thema in Spektrum der Wissenschaft):
– paralleles Rechnen, das heißt Arbeiten mit Computern, die mehrere gleichzeitig arbeitende Rechenwerke ("Prozessoren") enthalten (9/2002, S. 14);
– verteilte Berechnung: Ein Problem wird in Teile zerlegt und diese an zahlreiche voneinander getrennte Computer delegiert (6/2002, S. 80 und 7/2003, S. 66);
– Bildverarbeitung, insbesondere Erstellung von fraktalen Bildern (9/1989, S. 52);
– Datenkompression, deren praktische Bedeutung unablässig wächst (7/2001, S. 84);
– probabilistische Algorithmen, die voraussetzen, dass der Computer über echte Zufallszahlen verfügt (4/1994, S. 64);
– genetische Algorithmen, welche auf der aus der Evolution entlehnten Metaphorik von Variation und Selektion beruhen (9/1992, S. 44);
– neuronale Netze, deren Algorithmen für das automatische Lernen dem Lernen von lebenden Organismen nachempfunden sind (11/1992, S. 134);
– Analyse von Algorithmen zur Abschätzung ihrer Geschwindigkeit (4/1999, S. 76).

---

Der Gral der theoretischen Informatik


Eins der bedeutendsten Probleme der theoretischen Informatik ist die Faktorisierung. Es geht darum, eine natürliche Zahl in ihre Primfaktoren zu zerlegen. Beispiel: 123456789 = 3×3×3803×3607.

Trotz aller Fortschritte der letzten zwanzig Jahre kennt man bis heute kein Verfahren, mit dem man (selbst mit vernetzten Computern) in vernünftiger Rechenzeit Zahlen mit mehr als 200 Stellen faktorisieren könnte. Man vermutet, dass es keinen Algorithmus gibt, der eine n-stellige Zahl in einer Rechenzeit proportional zu n, zu n² oder auch nur zu n^p mit einer beliebigen natürlichen Zahl p faktorisieren könnte: Das Problem der Faktorisierung ist vermutlich nicht in polynomialer Rechenzeit zu lösen. Anders ausgedrückt: Das Faktorisierungsproblem gehört nicht zur Komplexitätsklasse P. Diese Vermutung ist bis jetzt noch unbewiesen.

Andererseits lässt sich die Korrektheit einer vorgelegten Primfaktorzerlegung ohne größere Mühe in polynomialer Zeit nachprüfen: Es ist nicht schwer nachzurechnen, dass 3×3×3803×3607=123456789 ist. Deshalb sagt man, dass das Faktorisierungsproblem zur Klasse NP gehöre. Die (irreführende) Bezeichnung NP bedeutet keineswegs "nicht in polynomialer Zeit lösbar", sondern "in polynomialer Zeit nachprüfbar".

Es scheint klar, dass die Klasse NP nicht mit der Klasse P zusammenfällt – denn es ist einfacher, eine bereits gefundene Lösung zu bestätigen als diese zu ermitteln! Dennoch gehört der Nachweis der Behauptung P NP zu den widerspenstigsten Rätseln der Komplexitätstheorie. Für ihren Beweis (oder den des Gegenteils) ist ein Preis von einer Million Dollar ausgesetzt. Als das Problem vor 25 Jahren formuliert wurde, hoffte man, es schnell lösen zu können. Diese Hoffnung hat bis heute getrogen, trotz aller Bemühungen (und der Attraktivität des Preises).

1994 revolutionierte Peter Shor die theoretische Informatik, als er einen Faktorisierungsalgorithmus mit polynomialer Zeit angab, der auf einem Quantencomputer laufen würde. Das löst nicht die Frage, ob P NP ist, zeigt aber, dass funktionsfähige Quantencomputer (die es heute noch nicht gibt) die Informatik und insbesondere die Kryptographie tief greifend verändern würden.

---

Ein neues Verständnis des Zufalls


Die Fortschritte der theoretischen Informatik haben tiefe Zusammenhänge zwischen Berechnung und Zufall offen gelegt. Dank der Arbeit der Theoretiker konnten drei Arten des Zufalls identifiziert werden:

- Der schwache Zufall ist das, was die Pseudo-Zufallszahlengeneratoren der gängigen Programmiersprachen erzeugen. Er ist ohne großen Rechenaufwand zu haben – geeignete Algorithmen liefern mehrere Millionen pseudozufälliger Stellen pro Sekunde – und genügt, um beispielsweise das Verhalten der Fahrzeuge im Straßenverkehr zu simulieren.

- Der kryptographische Zufall ist in seiner Erzeugung aufwendiger, aber unerlässlich für die Sicherheit in der Kryptographie. In diesem Gebiet wurden in den letzten 25 Jahren wichtige Resultate erzielt.

- Echten Zufall können Algorithmen nicht erzeugen – dennoch ist er nicht völlig unzugänglich. Die Komplexitätstheorie von Kolmogorow, ein für die theoretische Informatik fundamentales Gebiet, hat wertvolle Einsichten zu Tage gefördert. Echt zufällig ist eine Zeichenfolge, die "unbegreiflich" ist, das heißt nicht durch eine kürzere Zeichenfolge eindeutig beschrieben werden kann. Auch auf diesem Gebiet gab es in den letzten dreißig Jahren bedeutende Entwicklungen.

Aus: Spektrum der Wissenschaft 9 / 2003, Seite 20
© Spektrum der Wissenschaft Verlagsgesellschaft mbH