Spätestens seit seiner Lektüre von „Molecular Biology of the Gene“ war für Adleman eindeutig klar: Die DNA kann rechnen. Doch offensichtlich hatte die Natur in ihrer Milliarden Jahre dauernden Entwicklung zwar eine Fülle von natürlichen Informationsverarbeitungsmaschinen produziert, aber keine, die per se als Computerersatz taugte. Die DNA und RNA-Stränge und zahlreichen Enzyme machten ihren jeweiligen „Job“ perfekt, aber erschienen nicht gerade dazu geeignet, zwei Zahlen zu addieren oder als Schachcomputer Dienst zu tun.
Wenn Adleman also versuchen wollte, einen universell einsetzbaren DNA-Computer zu bauen, musste er die von der Natur vorgegebenen Werkzeuge zweckentfremden. Und um dabei die richtigen Strukturen und Techniken zu erproben, konnte dies nicht in einem großen Schritt geschehen, sondern nur Stück für Stück. Adleman: „Es galt klein anzufangen, mit einem DNA-Computer, der ein spezielles Problem löste – aber nicht zu speziell, damit das Potential der neuartigen Rechenmethode deutlich zutage trat.“
Auf der Suche nach einem geeigneten begrenzten Problem verfiel Adleman auf einen Klassiker unter den mathematischen Gedankenspielen – das Handlungsreisenden-Problem, auch „Hamiltonsche Wege“ genannt. Dieses vom irischen Hofastronom William Rowan Hamilton Mitte des 19. Jahrhunderts aufgestellte Denkspiel stellte die Aufgabe, von einem Startknoten ausgehend einen Weg zu einem Ziel zu finden und dabei auf dem Weg alle anderen vorgegebenen Stationen genau einmal zu berühren.
Oder weniger abstrakt ausgedrückt: Ein Handlungsreisender soll eine bestimmte Anzahl von Städten besuchen und dabei den kürzesten Weg zwischen ihnen finden. Die Schwierigkeit dabei: Nicht alle Städte sind über Direktflüge miteinander verbunden, es gibt auch „Einbahnstraßen“. Außerdem darf er jede Stadt nur einmal besuchen.
Während das Problem mit einer kleinen Anzahl von Städten noch leicht zu lösen ist, wächst die Schwierigkeit mit steigender Knotenzahl exponentiell an. Es gibt bereits Anordnungen mit 100 Knoten, bei denen selbst die schnellsten heutigen Supercomputer Millionen von Jahren bräuchten, um den Hamilton-Pfad herauszufinden. Unter Informatikern gilt dieses Problem daher als „NP-unvollständig“ – als nicht effizient mit einem Algorithmus zu lösen. Alle möglichen Algorithmen bestehen aus einer so großes Menge an Einzelschritten, dass Computer entweder extrem lange brauchen oder am Ende sogar ein falsches Ergebnis liefern würden.
Und genau dieses vertrackte Problem sollte nun die Rechenkünste der DNA beweisen…
Stand: 16.10.2001
