P-NP-Problem: Neuer Angriff auf das größte Rätsel der Informatik (2024)

Es gilt als das größte Rätsel der modernen Informatik. Der amerikanische Computerexperte Scott Aaronson hält es gar für die "tiefschürfendste Frage, die sich Menschen je gestellt haben". Nun hat der Bonner Mathematikprofessor Norbert Blum einen mathematischen Beweis ins Internet gestellt, der das Jahrhundertproblem lösen soll. "A Solution of the P versus NP Problem" ist 38Seiten lang und für Laien wohl nur schwer nachvollziehbar.

Demjenigen, der eine korrekte Lösung findet, winkt neben dem Ruhm auch viel Geld: Das so genannte P-NP-Problem zählt zu den sieben Millennium-Problemen, für deren Lösung das Clay Mathematics Institute im Jahr2000 eine Million US-Dollar in Aussicht gestellt hat.

Sollte Blums jetzt veröffentlichte Argumentation stimmen, wäre die Tragweite gewaltig: Der Forscher glaubt, beweisen zu können, dass P ungleich NP ist. Das wäre eine Enttäuschung für Zahlenforscher, eine Erleichterung für Kryptografen– und in jedem Fall ein Ergebnis für die Geschichtsbücher.

Auf die Komplexität kommt es an

Im Kern des P-NP-Problems steht die Frage, wie schnell ein Computer Aufgaben bestimmter Komplexität lösen kann. Informatiker unterscheiden hier P-Probleme und NP-Probleme. P-Probleme lassen sich in polynomieller Zeit berechnen. Man könnte auch sagen: Der Aufwand für die Lösung nimmt in vertretbarem Ausmaß zu, wenn der zu berechnende Input wächst. Mathematisch entspricht das der Beziehung nk, wobei n die Eingabelänge bezeichnet und k eine Konstante ist. Ein Beispiel ist die Frage, ob eine Zahl mit nZiffern eine Primzahl ist– das können moderne Algorithmen mit vergleichsweise wenigen Rechenschritten prüfen.

Anders sieht es aus, wenn der Aufwand für die Lösung eines Problems exponentiell anwächst, etwa nach dem Schema 2n. Solche Aufgaben werden teilweise so umfangreich, dass sie kein Rechner der Welt mehr mit vertretbarem Zeitaufwand lösen kann. Die Komplexitätsklasse NP ist hier nochmal ein Sonderfall: Sie umfasst "nichtdeterministisch polynomielle" Probleme. Darunter verstehen Informatiker Aufgaben, die mit deterministischen Rechnern rasant an Komplexität zuzunehmen scheinen.

Deterministisch ist ein Rechner dann, wenn er Rechenschritte nacheinander ausführt, und nicht alle denkbaren Lösungswege auf einmal ausprobieren kann– de facto sind also alle heutigen Computer deterministisch. Sie können bei einem NP-Problem zwar rasch überprüfen, ob eine Lösung stimmt. Die korrekte Lösung zu finden erfordert aber mitunter eine sehr lange Suche, schließlich muss ein deterministischer Rechner alle möglichen Wege sukzessive durchprobieren.

Ein extremes Beispiel für ein NP-Problem ist ein Handlungsreisender, der eine Reihe von Städten besuchen will, dabei aber eine möglichst kurze Strecke zurücklegen soll. Die Anzahl der Möglichkeiten, die ein Computer bei der Berechnung der kürzesten Strecke prüfen muss, wächst hier mindestens exponentiell mit der Zahl der zu besuchenden Städte. Ein Albtraum für jede Maschine. (Tatsächlich ist der Handlungsreisende so knifflig, dass Experten von einem NP-schweren Problem reden).

Für Mathematiker würde ein Traum platzen

Vielleicht gehen Informatiker Aufgaben wie diese aber auch einfach nur falsch an: Handelt es sich bei NP-Problemen in Wahrheit um Fragen, die sich mit Tricks in polynomieller Rechenzeit lösen ließen? Darauf liefe es hinaus, wenn P gleich NP ist. Das halten Informatiker für ziemlich unwahrscheinlich. Die Folgen wären allerdings gewaltig, denn auch das Knacken gängiger Verschlüsselungskodes ist ein NP-Problem. Würde es sich dabei in Wirklichkeit um ein P-Problem handeln, wäre es womöglich nur eine Frage der Zeit, bis Computer viele Kryptografieverfahren aushebeln, schreibt Scott Aaronson in einer Analyse des Problems.

Sollte der Beweis von Norbert Blum stimmen, könnten Computerexperten in aller Welt aufatmen. Für manchen Mathematiker würde hingegen wohl ein Traum platzen: Auch die Fahndung nach mathematischen Beweisen ist ein NP-Problem. Wäre P gleich NP könnte man die Lösungen zu einigen der anderen millionenschweren Millennium-Problemen also einfach von einem Computer suchen lassen.

Ob diese Möglichkeit mit Blums Beweis für alle Zeiten ausscheidet, müssen nun andere Informatiker und Mathematiker beurteilen. Einige von ihnen dürften bereits damit begonnen haben, die Argumentation des Bonner Wissenschaftlers zu prüfen. "Das ist eines der größten Probleme der Informatik überhaupt", sagt Günter Rote, Informatikprofessor von der Freien Universität Berlin.

Frühere Beweise waren schlichtweg unverständlich

​Erste Einschätzungen zu Blums Beweis sind schon im Internet aufgetaucht. Der Informatiker Luca Trevisan von der University of California in Berkeley glaubte am Tag nach der Veröffentlichung etwa, einen offensichtlichen Fehler in dem Paper gefunden zu haben, ruderte aber bald darauf zurück. In einem Blogpost skizziert er nun Blums Beweisidee und listet eine Reihe von möglichen Schwächen der Argumentation auf. Bald werde man wissen, ob derartige Einwände berechtigt sind, schreibt Trevisan.

Bei anderen Experten hinterließ die Arbeit hingegen einen guten Ersteindruck: "Hat jemand einen Fehler in dem Beweis gefunden? Norberts letzte Arbeit war großartig", kommentierte etwa der Computerforscher Reza Zadeh von der Stanford University auf Twitter. Ein anonymer Nutzer des Fachforums "Theoretical Computer Science Stack Exchange" hingegen vermerkte: Das Paper sei gut genug geschrieben, um entweder richtig oder falsch zu sein. Das hebe Blums Arbeit von vielen P-NP-Beweisen der Vergangenheit ab, die schlichtweg unverständlich gewesen seien.

Dem pflichtet Rote bei: "Wenn man den Beweis durchblättert, sieht das nicht sonderlich abschreckend aus, sondern so, als könnte man das ohne großen Aufwand nachvollziehen." Blum verwende im Wesentlichen mathematische Konzepte, die bereits seit zehn Jahren bekannt sind– und damit als erprobt gelten.

Es gibt bereits 116Beweise zu P-NP

Für manchen Experten ist das ein Grund, an der Arbeit des Bonner Forschers zu zweifeln. Solch ein großes Problem wie P-NP werde vermutlich durch überraschende neue Kniffe gelöst werden und nicht durch eine Abwandlung bekannter Rezepte, argwöhnte der Mathematiker Alon Amit auf der Plattform "Quora". Blums Ansatz ähnele dem zweier skandinavischer Computerwissenschaftler aus dem Jahr1999.

Mittlerweile hat sich auch Scott Aaronson zu Wort gemeldet, der vielen als Instanz in Sachen P-NP gilt: Er wette 200000US-Dollar darauf, dass der Beweis so wie alle früheren Versuche fehlerhaft ist, schrieb der Computerwissenschaftler von der University of Texas in Austin auf seinem Blog.

Tatsächlich haben in der Vergangenheit etliche Wissenschaftler Beweise zu dem berühmten Informatikproblem vorgelegt. GerhardJ. Woeginger von der RWTH Aachen hat alle bisherigen Versuche aufgelistet und kommt auf insgesamt 116Anläufe. Sie stellten sich letztlich alle als falsch heraus.

Blum selbst will sich noch nicht zu seinem Beweis äußern, teilt er auf Anfrage von "Spektrum.de" mit. Er wolle zunächst abwarten, was seine Fachkollegen zu seiner Arbeit sagen. "Er vertieft sich gerne in schwierige Probleme und löst diese allein", sagt der Berliner Informatiker Günter Rote über seinen Bonner Kollegen. Normalerweise dürfte der Kreis der Leute, die Blums Arbeit kritisch prüfen, überschaubar sein. Diesmal hat er sich aber ein Problem vorgenommen, das Computerexperten in aller Welt fasziniert. Wie ihr abschließendes Fazit ausfallen wird, ist derzeit noch offen.

P-NP-Problem: Neuer Angriff auf das größte Rätsel der Informatik (2024)

FAQs

P-NP-Problem: Neuer Angriff auf das größte Rätsel der Informatik? ›

P-NP-Problem Der Angriff auf das größte Problem der Informatik ist gescheitert. Vor drei Wochen glaubte der Bonner Professor Norbert Blum, das berühmte P-NP-Problem gelöst zu haben. Nun zieht er seinen Beweis zurück. Wochenlang waren Informatiker und Mathematiker in Aufruhr.

Was passiert wenn P NP ist? ›

Wenn P tatsächlich ungleich NP ist, dann gibt es Probleme, deren Lösungen zwar schnell überprüft (in NP), aber nicht schnell gefunden werden können (außerhalb von P).

Sind NP Probleme lösbar? ›

Bei NP-Problemen hingegen ist unbekannt, ob sie sich effizient lösen lassen oder nicht. Effizient bedeutet hierbei, dass die benötigte Rechenzeit eines Lösungsalgorithmus bei steigender Komplexität höchstens polynomiell (also zum Beispiel quadratisch) wächst.

Was bedeutet P Informatik? ›

Was ist die P Komplexitätsklasse? In der Informatik, speziell in der theoretischen Informatik und Computermathematik, ist die P Komplexitätsklasse ein fundamentaler Begriff beim Studium der Algorithmen und ihrer Laufzeit. Das Wort 'P' steht dabei für Polynomialzeit.

Sind alle Probleme in NP Entscheidbar? ›

NP-vollständige Probleme

So bezeichnet man die schwersten Probleme in der Klasse NP, zur Zeit etwa 2000. Sie sind entscheidbar. Es ist ein Polynomialzeit-Algorithmus zur Überprüfung der Lösung bekannt.

Welche Probleme sind NP-vollständig? ›

Ein Problem gilt als NP-vollständig, wenn es zuerst in der Klasse NP liegt – also nichtdeterministisch in polynomieller Zeit lösbar ist – und zweitens jedes andere Problem in NP auf dieses Problem in polynomieller Zeit reduzierbar ist.

Wie heißt eines der größten ungelösten Probleme der Theoretischen Informatik? ›

Geschichte. Erkannt wurde das P-NP-Problem zu Beginn der 1970er Jahre durch unabhängige Arbeiten von Stephen Cook und Leonid Levin. Es gilt als eines der wichtigsten ungelösten Probleme der Informatik und wurde vom Clay Mathematics Institute in die Liste der Millennium-Probleme aufgenommen.

Ist das Halteproblem NP schwer? ›

NP ist die Klasse der nachweis-polynomiellen Probleme. NP-vollständige Probleme sind die schwersten Probleme in NP: Wenn man eines davon effizient löst, dann kann man alle Probleme in NP effizient lösen. SAT ist NP-vollständig und HornSAT ist P-vollständig.

Sind Sprachen in NP Entscheidbar? ›

Da jede Sprache aus NP entscheidbar ist (man kann eine deterministische Turingmaschine konstruieren, die stets hält und genau die Sprache akzeptiert), ist auch jede NP-vollständige Sprache entscheidbar.

Ist das Sat Problem entscheidbar? ›

2-SAT ist in Linearzeit entscheidbar.

Für was steht P bei Wahrscheinlichkeit? ›

Für die Wahrscheinlichkeit für das Eintreten eines Ereignisses A schreibt man meistens P ( A ) P(A) P(A) (das P kommt vom englischen Wort probability). Je höher P ( A ) P(A) P(A) ist, desto wahrscheinlicher ist, dass bei diesem Zufallsexperiment das Ereignis A eintreten wird.

Was ist P in Mathe Funktion? ›

steht p kurz für den p-Wert. steht. in der Mengenlehre für die Potenzmenge.

Ist P eine Teilmenge von NP? ›

P ist sicher eine Teilmenge von NP. Es gehört jedoch zu den wichtigsten ungelösten Fragen der theoretischen Informatik, ob P = NP gilt (siehe auch P-NP-Problem). P ist unter Komplementbildung abgeschlossen.

Was macht NP? ›

NP (Nichtdeterministisch Polynomialzeit) ist die Klasse der Entscheidungsprobleme, die in Polynomialzeit von einer nichtdeterministischen Turingmaschine gelöst werden können. NP-vollständig: Ein Problem ist NP-vollständig, wenn es in NP liegt und alle Probleme in NP in Polynomialzeit auf es reduziert werden können.

Was ist ein Problem Informatik? ›

Ein Problem ist eine nicht routinemäßig lösbare Aufgabe. Eine Aufgabe dagegen ist mit bekannten Werkzeugen routinemäßig zu lösen. Das Ziel der Problemlösestrategien in der Informatik ist es, eine allgemein gültige Verarbeitungsvorschrift für eine Klasse von Problemen zu finden.

Was müssen Sie tun Wenn Sie ein Problem als NP-vollständig nachweisen wollen? ›

F: Was müssen Sie tun, wenn Sie ein Problem als NP-vollständig nach- weisen wollen? A: Zeigen, dass es in NP ist und zeigen, dass jedes Problem aus NP sich auf dieses Problem in Polynomialzeit reduzieren lässt.

Was ist NP schwer? ›

NP-schwer sind hingegen Probleme, die mindestens so schwierig sind wie das härteste Problem in NP. Eine wichtige Unterscheidung ist jedoch, dass NP-schwere Probleme nicht notwendigerweise in NP liegen müssen. Alle NP-vollständigen Probleme sind NP-schwer, aber nicht alle NP-schweren Probleme sind NP-vollständig.

Was heißt P bei Wahrscheinlichkeit? ›

Die Wahrscheinlichkeit (auf Englisch probability) ist also ein Maß, das bestimmt wie sehr erwartet wird, dass genau dieses Ereignis eintritt. Mathematisch geschrieben wird die Wahrscheinlichkeit des Ereignisses X ausgedrückt als P(X). Sie kann Werte im Bereich zwischen [0,1] annehmen.

Ist es möglich für jedes Problem in NP eine polynomiale Lösung zu finden? ›

Mit Hilfe von A kann somit jedes Problem in NP in Polynomialzeit entschieden werden. Angenommen, es gilt P = NP. Die stark NP-vollständigen Probleme sind eine Teilmenge der NP-vollständigen Probleme. Es existiert also ein Algorithmus A, der polynomiale Lauf- zeit in n benötigt.

Top Articles
Latest Posts
Article information

Author: Terrell Hackett

Last Updated:

Views: 5994

Rating: 4.1 / 5 (72 voted)

Reviews: 87% of readers found this page helpful

Author information

Name: Terrell Hackett

Birthday: 1992-03-17

Address: Suite 453 459 Gibson Squares, East Adriane, AK 71925-5692

Phone: +21811810803470

Job: Chief Representative

Hobby: Board games, Rock climbing, Ghost hunting, Origami, Kabaddi, Mushroom hunting, Gaming

Introduction: My name is Terrell Hackett, I am a gleaming, brainy, courageous, helpful, healthy, cooperative, graceful person who loves writing and wants to share my knowledge and understanding with you.