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.
