Aufwand und Reibung

Warum ein zu treibender Aufwand und eine zu überwindende Komplexität nicht unbedingt schlecht sind.

 

Silvester und ein sehr kluger Artikel von Lance Fortnow:  Fifty Years of P vs. NP and the Possibility of the Impossible, in den Communications of the ACM, Januar 2022, regte mich zu diesem Artikel an, der für weite Bevölkerungskreise wichtige Konzepte der Informatik und der Physik erstmals in Beziehung setzt. Aber Moment mal, wie viele Leute meine Glossen lesen, weiß ich überhaupt nicht, da der Webseitenbetreiber keine Analyse der Zugriffe macht, und Sie, liebe Leser, so gut wie nie Kommentare absondern.

Als erstes ist das informatische Konzept der Komplexität eines Problems zu erklären. Die Komplexität ist der notwendige Aufwand, meist die Anzahl der Rechenschritte, um das Problem zu lösen. Die Komplexität wird als eine Funktion der Größe n der Eingabe angegeben. Nehmen wir das Problem des Handlungsreisenden: Es gilt, eine optimale Route durch n vorgegebene Städte zu finden, auf denen jede Stadt genau einmal besucht wird. Man könnte dasselbe abstrakte Problem auch als das Problem des Haremsreisenden verkleiden. Dann hätten wir den Besitzer eines verteilten Harems, der in jeder der n Städte eine Geliebte hat, die er alle auf einer Tour genau einmal – ja darf man es heute noch sagen? – erfreuen möchte.

In dieser Verkleidung hätte man eine erste natürliche Verbindung zum physikalischen Konzept der Reibung und ihrer Wichtigkeit für den Bestand der menschlichen Rasse. Das Problem des Handlungsreisenden ist das prototypische Problem, das genannt wird, wenn man die N vs. NP-Frage erläutern möchte. Dabei sind P und NP zwei sogenannten Komplexitätsklassen, d.h. Klassen von Problemen, deren Lösung denselben Aufwand erfordert. P ist die Klasse der Probleme, die deterministisch mit polynomiellem, also erträglichem Aufwand gelöst werden kann. Es gäbe also für jedes Problem in P ein Programm, welches z.B. n2 oder n3 Schritte zur Lösung braucht. Die Klasse NP besteht aus den Problemen, wo man eine vorgeschlagene Lösung mit ploynomiellem Aufwand auf Richtigkeit überprüfen kann. Möchte man ein Programm schreiben, das Lösungen berechnet, dann würde es vermutlich exponentiellen Aufwand brauchen. Das ist die PNP-Vermutung. Das Problem des Handlungsreisenden ist vermutlich nicht in der Komplexitätsklasse P, es ist aber in der Klasse NP.

Das physikalische Konzept der Reibung kennt ein jeder. Reibung verlangsamt Fahrzeuge, wenn man bremst, sie lässt rotierende, nicht angetriebene Räder zum Stillstand kommen, selbst Luft verursacht Reibung an einem Flugzeug, einem PKW und an einem Fahrrad samt Fahrer.

Beides, Komplexität wie Reibung, klingen erst einmal negativ, sie vernichten Energie, die eine durch das Ausführen von Berechnungen, die andere durch die Überwindung von Reibung. Allerdings scheinen beide auch für ein normales Leben notwendig zu sein.

Da komme ich wieder auf Silvester zurück. Vor vielen Jahren gab es zu Silvester Blitzeis. Die Straßen waren also spiegelglatt. Eine leichte Steigung der Straße, nicht weit von unserem Haus entfernt, bot also den Füßen so gut wie keine Reibung. Verzweifelte Fußgänger, welche die Straße hoch wollten, versuchten das auf allen Vieren, um wenigstens etwas Reibung zu entwickeln und damit Halt zu haben. In einer Welt ohne Reibung wäre Fortbewegung nur auf präparierten Oberflächen möglich, in denen die Füße, Schuhe bzw. Räder Halt finden könnten. Jede Eisen-, jede Straßenbahn wäre eine Zahnradbahn.

Wir sehen, dass Reibung unser Leben manchmal auch erleichtert. Weshalb aber ist eine nicht zu vernachlässigende Komplexität eventuell wünschenswert? Stellen wir uns eine Welt vor, in der ein blitzschneller Algorithmus zur Gesichtserkennung jeden uns entgegenkommenden Menschen sofort identifiziert, ein ebenso blitzschnelles maschinelles Lernverfahren die vorliegenden Daten über diesen Menschen analysiert, dabei seine politische Einstellung, seine sexuellen Vorlieben, seine Hobbys und insbesondere den Zusammenhang zwischen jeweils gezeigtem Verhalten und dahinterstehenden Intentionen präzise erfasst, und anschließend auf Mimik und Gestik des Menschen anwendet. Der Arme hätte schlicht keine Chance mehr.

Noch naheliegender ist es, die Auswirkung mangelnder Komplexität auf unsere Kryptoinfrastruktur zu sehen. Die meisten Verschlüsselungsverfahren beruhen darauf, dass ein Problem schwer, d.h. nur mit exponentiellem Aufwand lösbar ist, zum Beispiel das Problem, große Zahlen in ein Produkt von Primzahlen zu zerlegen. Wenn man diese Probleme schnell lösen könnte, könnte man auch verschlüsselte Nachrichten schnell entschlüsseln, der Traum aller Geheimdienste. Sie müssten dann nicht mal von den Herstellern unserer Geräte eingebaute Hintertüren ausnutzen.

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert.

Ähnliche Artikel