Seit Anfang des Jahrtausends gibt es für sieben Probleme, welche die Zukunft verändern können, jeweils ein Preisgeld von einer Million US-Dollar.
Diese Probleme heißen Millenniums-Probleme und sind die schwierigsten mathematischen Probleme unsere Zeit. Bisher ist es nur bei einem Problem, der Poincare-Vermutung, gelungen eine Lösung zu bestimmen.
Das P-NP-Problem, das als das Einfachste galt, bleibt aber weiterhin ungelöst.[1]

Das P-NP Problem

Die Komplexitätstheorie beschäftigt sich mit dem Umfang von Algorithmen. Diese werden in 2 verschiedene Arten unterteilt. Polynomielle (P) und nicht-deterministisch-polynomielle (NP).[2]

Polynomielle Algorithmen sind schnell lösbar im Vergleich zu nicht-deterministisch-polynomiellen, weil sie eine festgelegte Anzahl an Rechenschritten haben.
Bei der Berechnung von nicht-deterministisch-polynomielle Algorithmen müssen beliebig viele Rechenpfade erzeugt werden, von denen aber nur ein Pfad Erfolg haben muss.[3]

Die große Frage ist, ob alle nicht-deterministisch-polynomielle Algorithmen auch mit dem Aufwand von polynomiellen Algorithmen gelöst werden könnten.[4]

Die Auswirkung von P=NP

Wenn P=NP ist hieße das, es gäbe für jedes Problem einen Algorithmus der dieses in einer vergleichsweisen kurzen Zeit lösen könnte, aber noch nicht entdeckt ist.
Zu diesen schnell lösbaren Problemen zählen auch Verschlüsselungen. Es gibt also zu jeder Verschlüsselung oder Chiffrierung einen schnellen Weg, diese zu lösen. Online Banking oder Kryptowährungen wären nicht mehr sicher und verschlüsselte Nachrichten könnten wieder entschlüsselt werden. Moderne Verschlüsselungen sind momentan nur sicher, weil es mit den aktuellen Algorithmen teilweise Millionen von Jahren dauern würde, diese zu entschlüsseln.[5]

Die Auswirkungen von P!=NP

Das umgekehrte Ergebnis würde bedeuten, es gäbe keinen kürzeren Rechenweg bei nicht-deterministisch-polynomielle-Algorithmen. Um diese Probleme lösen zu können, müsste mehr Rechenkapazität zu Verfügung gestellt werden, um die größere Anzahl an Rechenschritten dennoch in akzeptabler Zeit zu bearbeiten. [6]

 

Lösungsversuche

Im August 2017 ist der bis jetzt letzte Lösungsvorschlag beim Clay Mathematics Institute (CMI) eingereicht worden. Er kommt von dem Bonner Mathematiker und Professor Norbert Blum. Mittlerweile hat aber auch er seinen Beweis zurückgezogen.  Der Mathematiker Gerhard Woeginger von der RWTH Aachen listet bereits 116 fehlgeschlagene Beweisversuche auf seiner Homepage auf. Diese Thesen versuchen sowohl P=NP, als auch P!=NP zu beweisen. [7]

Beweis

Für einen P=NP-Beweis müsste für jeden nicht-deterministisch-polynomiellen-Algorithmus eine polynomielle Alternative gefunden werden[8] oder für einen P!=NP-Beweis gezeigt werden, dass es keinen polynomiellen Algorithmus als Alternative zu einem nicht-deterministisch-polynomiellen geben kann. [9]

Egal welche Lösung sich als wahr herausstellen wird, sie wird definitiv weitreichende Folgen für die Computerwissenschaft haben und sie noch lange prägen. [10]

 

[1] { o.V. 2014, Die sechs ungelösten Rätsel der Mathematik }

[2] { Martin Grötsche 2005, Das Problem mit der Komplexität }

[3] { o.V. 2017, P und NP }

[4] {Christian Speicher 2017, Das berühmte «P versus NP»-Problem ist doch nicht geknackt }

[5] {Robert Gast und Manon Bischoff 2017, Neuer Angriff auf das größte Rätsel der Informatik }

[6] {Martin Grötsche 2005, Das Problem mit der Komplexität }

[7] {Robert Gast und Manon Bischoff 2017, Neuer Angriff auf das größte Rätsel der Informatik }

[8] {Manon Bischoff 2017, Der Angriff auf das größte Problem der Informatik ist gescheitert }

[9] { o.V. 2017, P und NP }

[10] {Manon Bischoff 2017, Der Angriff auf das größte Problem der Informatik ist gescheitert }

 

____

Verfasst von Jan-Niklas Enders im Rahmen der Bachelorveranstaltung “Mobile Anwendungen und Systeme” im Fachbereich Informatik, Studiengang Wirtschaftsinformatik, bei Frau Prof. Dr. U. Gröner an der Fachhochschule Dortmund, Veröffentlicht am 05.01.2018

____

 

Literaturverzeichnis

Christian Speicher (2017): Das berühmte «P versus NP»-Problem ist doch nicht geknackt. Hg. v. Neue Züricher Zeitung AG. Online verfügbar unter https://www.nzz.ch/wissenschaft/mathematik-das-beruehmte-p-versus-np-problem-ist-doch-nicht-geknackt-ld.1314458, zuletzt aktualisiert am 05.09.2017, zuletzt geprüft am 06.12.2017.

Manon Bischoff (2017): Der Angriff auf das größte Problem der Informatik ist gescheitert. P-NP-PROBLEM. Hg. v. Spektrum.de. Online verfügbar unter http://www.spektrum.de/news/der-angriff-auf-das-groesste-problem-der-informatik-ist-gescheitert/1498831, zuletzt aktualisiert am 01.09.2017, zuletzt geprüft am 06.12.2017.

Martin Grötsche (2005): Das Problem mit der Komplexität: P = N P? Hg. v. Zuse Institute Berlin (ZIB). Zuse Institute Berlin (ZIB). Online verfügbar unter https://www.zib.de/groetschel/pubnew/paper/groetschel2007b_pp.pdf, zuletzt geprüft am 06.12.2017.

o.V. (2014): Die sechs ungelösten Rätsel der Mathematik. Millenium-Rätsel. Hg. v. forschung-und-wissen.de. Online verfügbar unter https://www.forschung-und-wissen.de/magazin/forschung-technologie/die-sechs-ungeloesten-raetsel-der-mathematik-13371943, zuletzt aktualisiert am 19.06.2017, zuletzt geprüft am 06.12.2017.

o.V. (2017): P und NP. Für Laien erklärt. Hg. v. http://nkblog.nkdev.de. Online verfügbar unter http://nkblog.nkdev.de/p-und-np-fur-laien-erklart/, zuletzt aktualisiert am 09.08.2017, zuletzt geprüft am 06.12.2017.

Robert Gast und Manon Bischoff (2017): Neuer Angriff auf das größte Rätsel der Informatik. P-NP-PROBLEM. Hg. v. Spektrum.de. Online verfügbar unter http://www.spektrum.de/news/loesung-fuer-p-np-problem/1494941, zuletzt aktualisiert am 16.08.2017, zuletzt geprüft am 06.12.2017.