Stell dir vor, du bist ein Dieb raubt einem museum ausstellen von verlockenden Schmuck, Drusen und seltenen Edelsteinen. Du bist neu darin, also hast du nur einen einzigen Rucksack mitgebracht. Ihr Ziel sollte es sein, mit den wertvollsten Gegenständen davonzukommen, ohne Ihre Tasche zu überlasten, bis sie zerbricht oder zu schwer zum Tragen wird. Wie wählen Sie unter den Objekten, um Ihre Beute zu maximieren? Sie können alle Artefakte und ihre Gewichte auflisten, um die Antwort von Hand herauszufinden., Aber je mehr Objekte es gibt, desto mehr Besteuerung wird diese Berechnung für eine Person—oder einen Computer.
Dieses fiktive Dilemma, das „Knapsack-Problem“, gehört zu einer Klasse mathematischer Probleme, die dafür bekannt sind, die Grenzen des Rechnens zu überschreiten. Und das Rucksackproblem ist mehr als ein Gedankenexperiment. „Viele Probleme, mit denen wir im Leben konfrontiert sind, sei es Geschäft, Finanzen, einschließlich Logistik, Containerschiffladung, Flugzeugladung — das sind alles Rucksackprobleme“, sagt Carsten Murawski, Professor an der Universität von Melbourne in Australien., „Aus praktischer Sicht ist das Rucksackproblem im Alltag allgegenwärtig.“
Die Forscher nutzten einst die Komplexität des Problems, um Computersicherheitssysteme zu erstellen, aber diese können jetzt geknackt werden, da das Problem so gut untersucht wurde. Heute, da Technologie, die in der Lage ist, die Schlösser unserer digitalen Kommunikation zu zerstören, am Horizont auftaucht, kann das Rucksackproblem neue Wege zur Vorbereitung auf diese Revolution inspirieren.
Alles oder nichts
Das Rucksackproblem gehört zu einer Klasse von“ NP “ – Problemen, die für „nichtdeterministische Polynomzeit“ steht.,“Der Name verweist darauf, wie diese Probleme einen Computer dazu zwingen, viele Schritte zu unternehmen, um zu einer Lösung zu gelangen, und die Anzahl steigt dramatisch an, basierend auf der Größe der Eingaben—zum Beispiel dem Inventar der Artikel, aus denen beim Füllen eines bestimmten Rucksacks ausgewählt werden muss. Per Definition haben NP-Probleme auch Lösungen, die leicht zu überprüfen sind (es wäre trivial zu überprüfen, ob eine bestimmte Liste von Elementen tatsächlich in einen Rucksack passt).,
„Das Problem, das die Theoretiker zu untersuchen begannen, war, wie effizient eine bestimmte Aufgabe auf einem Computer ausgeführt werden kann“, schreibt Keith Devlin in dem Buch The Millennium Problems. Zum Beispiel: Bei einer Liste von 1 Million Museumsartefakten mit ihren Gewichten und Geldwerten und einem auf 25 Pfund begrenzten Rucksack müsste ein Computer jede mögliche Kombination durchlaufen, um die einzige mit der lukrativsten Strecke zu generieren. Angesichts einer unbestimmten Zeit könnte ein Computer Brute-Force verwenden, um große Fälle wie diese zu optimieren, aber nicht auf Zeitskalen, die praktisch wären.,
„Wir denken, Sie könnten die gesamte Erde mit Prozessoren abdecken und sie bis zum Hitzetod des Universums ausführen und immer noch relativ kleine Instanzen geeigneter Versionen dieser Probleme nicht lösen“, sagt Noah Stephens-Davidowitz, Microsoft Research Fellow am Simons Institute in Berkeley, Kalifornien.
Einige NP-Probleme wie das Knapsack-Beispiel haben eine besondere Eigenschaft: In den frühen 1970er Jahren zeigten Stephen Cook und Richard Karp, dass eine Vielzahl von NP-Problemen in ein einziges Problem der formalen Logik umgewandelt werden konnte., Wenn man also effizient mit einem Algorithmus gelöst und verifiziert werden könnte, könnten sie alle. Diese Eigenschaft wird als „NP“ bezeichnet.“
Eine der hartnäckigsten Fragen in der Informatik und Mathematik ist, ob sich diese „NP“ – Probleme, einschließlich des Rucksackproblems, wirklich von „P“ – Problemen unterscheiden, die in der sogenannten Polynomzeit gelöst werden können. Wenn P=NP, dann ist es möglich, jedes Problem zu lösen, dessen Lösungen leicht zu überprüfen sind, sagt Stephens-Davidowitz. Wenn diese Ungleichheit also anhält, wird das allgemeine Rucksackproblem immer schwer sein.,
Dinge geheim halten
Kryptografieforscher lieben Probleme, die für Computer schwer zu lösen sind, da sie beim Verschlüsseln digitaler Nachrichten nützlich sind. Knapsack-Problem-ähnliche Sicherheitscodes sind dafür nicht nützlich, da sie zu leicht zu knacken sind, aber kompliziertere Methoden, die von diesem Problem inspiriert sind, werden entwickelt und können eines Tages eine Rolle bei der Überlisten der nächsten Generation von Computern spielen.,
Bei einer frühen Verschlüsselungsmethode im Knapsack-Stil wäre der private Schlüssel einer Person eine Liste von Zahlen, in denen jede größer ist als die Summe ihrer Vorgänger. Der Austausch mit dieser Person würde einen öffentlichen Schlüssel verwenden, der zufällig aussieht, aber aus Zahlen aus der ersten Liste besteht, auf die bestimmte Transformationen angewendet werden. Wenn der öffentliche Schlüssel beispielsweise ist, wird die übertragene Nachricht „1, 0, 0, 1“ codiert als 2+0+0+5 = 7 (weil 2*1=2, 3*0=0, 4*0=0, und 5*1=5). Geheime Nummern, die an den Konvertierungen zwischen Schlüsseln beteiligt sind, ermöglichen die Enthüllung der ursprünglichen Nachricht.,
Damit dies funktioniert, muss ein Computer auch herausfinden, ob eine bestimmte Zahl als Summe einer Teilmenge von Zahlen in den privaten Schlüssel geschrieben werden kann, was zu einem einfachen Rucksackproblem wird. Es ähnelt dem Füllen eines Rucksacks mit einer Charge von Gegenständen unterschiedlicher Größe — wie einem Ring, einem Gemälde, einem Auto und einem Haus — und dem Wissen, dass Sie nichts anderes hineinstopfen können, nachdem Sie überprüft haben, ob der Ring und das Gemälde passen. Die Kryptographen Ralph Merkle und Martin Hellman beschrieben diese Idee 1978, aber andere fanden heraus, wie man sie Anfang der 1980er Jahre knackt.,
Der private Informationsaustausch im heutigen Internet verwendet häufig Schlüssel mit großen Primzahlen, und obwohl es schwierig ist, große Zahlen zu berücksichtigen, wird nicht angenommen, dass sie zu derselben „NP complete“ – Klasse gehören wie das Knapsack-Problem. Informatiker bereiten sich jedoch bereits auf eine Zukunft vor, in der Quantencomputer diese Schlüssel schnell entsperren können.
Quantencomputer stützen sich auf die Prinzipien der Quantenmechanik, die besagt, dass sich ein Teilchen nicht in einer einzigen Position befindet, sondern eine Wahrscheinlichkeit hat, an vielen verschiedenen Orten zu sein, es sei denn, es wird festgehalten und gemessen., Während normale Computer Informationen in 0s und 1s kodieren, würde jedes „Qubit“ in einem Quantencomputer eine breite Palette möglicher Zustände aufweisen, die sich auf die Eigenschaften von Teilchen beziehen. Quantencomputer wären nicht nützlich, um im Internet zu surfen oder ein Drehbuch in einem Café zu schreiben, aber sie würden nie zuvor gesehene Leistung bei einigen Arten von mathematischen Problemen freisetzen. Leider bilden diese mathematischen Probleme die Grundlagen der modernen Cybersicherheit.
„In gewisser Weise hatten wir wirklich Pech“, sagt Stephens-Davidowitz., „Wir haben es geschafft, die Sicherheit des Internets auf der Härte einiger der wenigen Probleme auszuruhen, die für klassische Computer schwierig, für Quantencomputer jedoch einfach zu sein scheinen.“
Während das Quantencomputing in den Kinderschuhen steckt, sagen einige Forscher, dass wir uns darauf vorbereiten. Im Jahr 2016 forderte das National Institute of Standards and Technology (NIST) neue quantenresistente Verschlüsselungsmethoden und kündigte im vergangenen Jahr 26 Halbfinalisten an. Eine solche Art von Algorithmus, der entwickelt wird, wird gitterbasierte Kryptographie genannt., Anstatt Zahlen zu verwenden, werden Schlüssel verwendet, die in mehreren Dimensionen vorhanden sind und die Bildung einer Gitterstruktur aus gleich großen Punkten im Raum beinhalten. Die Frage ist, wo diese Punkte sind und wie nahe ein gegebener zufälliger Punkt an den Koordinaten eines Gitters ist. In seinem Herzen ist dies ein Rucksackproblem in mehr als einer Dimension.
„Meine derzeitige Besessenheit ist zu versuchen, herauszufinden, wie sicher diese lattice-based Dinge sind es, die-idealerweise bevor wir verwenden Sie zum ausführen des internet,“ Stephens-Davidowitz sagt.,
„Das bedeutet, wir müssen quantum-resistant cryptography viel früher als wir erwarten, Quanten-computer, um Ihr volles Potenzial erreichen“, sagte Leo Ducas, ist wissenschaftliche Mitarbeiterin am Centrum Wiskunde & Informatica in den Niederlanden.
Über die Kryptografieforschung hinaus sind das Knapsack-Problem und seine vollständigsten Cousins überall im wirklichen Leben. Zum Beispiel haben Sie vielleicht von dem Problem „reisender Verkäufer“ gehört, das ebenfalls nicht vollständig ist., Die Herausforderung besteht darin, den kürzesten Weg für einen Verkäufer zu finden, um zwischen einer bestimmten Anzahl von Städten zu reisen, bevor er zum Ausgangspunkt zurückkehrt. Eng verwandt ist das Problem der Fahrzeugführung, das mehrere Fahrzeuge berücksichtigt, die Lieferungen durchführen.
Luciana Buriol, außerordentliche Professorin an der Universidade Federal do Rio Grande do Sul in Brasilien, hat dieses Problem angegriffen, um neue Ansätze für den Gesundheitssektor zu finden., Sie arbeitete mit einem häuslichen Pflegedienst zusammen, bei dem Ärzte und Krankenschwestern Patienten in ihren Häusern besuchen, und half bei der Optimierung ihrer Routen, da eine begrenzte Anzahl von Autos für den Transport zur Verfügung stand.
„Angesichts von 300 Patienten und 15 Autos können Sie die Lösung nicht in angemessener Zeit finden“, sagte sie. „Wenn Sie Tage haben, um den Algorithmus auszuführen, werden Sie ihn finden-aber Sie müssen ihn in weniger als 2 Stunden finden, sonst werden Sie ihn nie in der Praxis verwenden.“
Kein einziger One-size-fits-all-Algorithmus kann diese Probleme lösen., Stattdessen findet Buriol schnelle Wege, um zu nützlichen Annäherungen zu gelangen, damit sie in die Tat umgesetzt werden können.
Rucksäcke um uns herum
Für diejenigen von uns, die keine Informatiker sind und im wirklichen Leben mit solchen Problemen konfrontiert sind, wie gut sind wir? Murawskis Gruppe findet vorläufige Ergebnisse, dass, wenn man Menschen Knapsack-ähnliche Probleme gibt, wir auch mächtig kämpfen., In kleinen Experimenten, in denen die Teilnehmer gebeten wurden, einen Rucksack auf einem Computerbildschirm mit Gegenständen mit angegebenen Werten und Gewichten zu füllen, fiel es den Menschen tendenziell schwerer, den Inhalt des Rucksacks zu optimieren, da die Anzahl der Artikeloptionen zunahm—das gleiche Problem haben Computer. Die Forscher sagen, dass dieser Befund mit einer „Wahlüberlastung“ zusammenhängen kann: Der Art und Weise, wie wir einfrieren, wenn wir zu viele Möglichkeiten haben, selbst in einfachen Situationen wie dem Kauf von Marmelade in einem Lebensmittelgeschäft.
Doch in der realen Welt kommen wir durch. Aufmerksamkeit ist auch ein Rucksackproblem., Beim Fahren stehen wir vor einem Füllhorn möglicher Ablenkungen wie Vögeln, Wolken, dem Radio und umliegenden Gebäuden. Wir müssen nur die relevantesten Reize in unsere mentalen Rucksäcke stecken—und im Allgemeinen tun wir das.
Die Frage bleibt: Da NP vollständige Probleme für Computer schwieriger sind als andere Arten von Rätseln, sind sie auch für Menschen schwieriger? Die begrenzten ersten Ergebnisse deuten darauf hin, dass sie sein könnten, was Murawski überraschte.,
„Wenn sich herausstellt, dass dies der Fall ist, würde dies darauf hindeuten, dass die Härte solcher Probleme ein Merkmal der Probleme ist—eine Eigenschaft der Natur—und nicht im Auge des Betrachters“, sagt Murawski.