Auf Thema antworten

Am 11. August 2017 veröffentlichte Blum einen Preprint, in dem er behauptet, die Lösung des P-NP-Problems gefunden zu haben in dem Sinn, dass die Komplexitätsklassen P und NP verschieden sind.[4] Darin wird eine superpolynomiale (exponentielle) untere Schranke für nicht-monotone Schaltkreiskomplexität für das NP-schwere Cliquenproblem angegeben. Für monotone Boolesche Funktionen (das heißt solche ohne Negation) war eine superpolynomiale untere Schranke zuerst von Alexander Rasborow in den 1980er-Jahren angegeben worden, für nicht-monotone (die die Berechenbarkeits-Mächtigkeit von Turingmaschinen haben und für die der Nachweis einer solchen Schranke das P-NP-Problem lösen würde) war man aber seitdem erfolglos geblieben.

Blum baut seine Theorie auf einer Approximationsmethode von Rasborow auf, mit einer im Vergleich zu Rasborow abgeschwächten Distanzfunktion (Rasborow konnte mit seiner Distanzfunktion nur quadratische untere Schranken bei der nicht-monotonen Schaltkreiskomplexität beweisen), und auf Arbeiten von Christer Berg und Staffan Ulfberg (1999) sowie Kazuyuki Amano und Akira Maruoka (2004) bei deren Beweis einer exponentiellen unteren Schranke der monotonen Netzwerkkomplexität beim Cliquenproblem. Dass man mit Negation, also nicht-monotonen Booleschen Funktionen, die Schaltkreiskomplexität eines NP-schweren Problems nicht von exponentiell auf polynomial senken könne, war schon zuvor allgemein vermutet worden. Eine Verifikation oder Widerlegung des Beweises steht noch aus. Vor Blum hatten schon zahlreiche andere Wissenschaftler Beweise vorgeschlagen, die sich später als fehlerhaft herausstellten.[5]

(https://de.wikipedia.org/wiki/Norbert_Blum)

Hinweis: Es geht nicht um die Rentensicherung nach Norbert Blüm im Rahmen des Verkohlungsproblems.

Salam!