P vs. NP: Das MILLIONEN Dollar PROBLEM der Informatik

Eine der wichtigsten und ältesten Fragen der Informatik ist das so genannte "P vs NP“-Problem.

*Kapitel:*
00:00 Einführung
04:33 Auswirkungen des P / NP Problems
6:58 Techniken zum Beweisen von P / NP
10:30 Aktueller Stand der Forschung
13:05 Schlusswort

* *Meine Website mit allen anderen Kanälen und Newsletter* *:

_Discord:_

_Unterstützt mich - Danke!:_

[AmagoThePlayer]

In unserem Skript zur Komplexitätstheorie steht folgendes meiner Meinung nach sehr interessantes Zitat dazu von Scott Aaronson:

If P=NP, then the world would be a profoundly different place than we usually assume it to be.

There would be no special value in “creative leaps, ”
no fundamental gap between solving a problem and
recognizing the solution once it’s found.

Everyone who could appreciate a symphony would be Mozart.
Everyone who could follow a step-by-step argument would be Gauss.
Everyone who could recognize a good investment strategy would be Warren Buffett.

[reinerczerwinski]

5:00 Es kann sein, das P ungleich NP ist, aber Faktorisierung schnell lösbar ist, da Fakorisierung höchstwahrscheinlich nicht NP-schwer ist

[Hofer]

So könnte man das Erfüllbarkeitsproblem lösen:
Setze am Anfang den Wert aller Variablen auf 0.5
Setze dann nacheinander den Wert einer Variablen auf 0 bzw. 1
Ist der Wert des Gesamtausdrucks gleich 1, so ist er offensichtlich für diese Belegung erfüllbar.
Ist er gleich 0, so ist er, ebenso offensichtlich, für diese Belegung nicht erfüllbar.
Nimm dann so viele Gesamtausdrücke, bis deren Summe größer gleich 1 ist.
Wiederhole den Vorgang sinngemäß.

So kann man auch händisch die Erfüllbarkeit für beispielsweise 20 Variablen ermitteln. Zumindest sollte das oft gelingen.

[SebastianSchellhorn]

Schönes Video. Eine Korrektur zum Satz, dass man sich alle Kombinationen möglicher Variablenbelegungen anschauen muss, um eine Lösung für ein SAT-Problem zu finden: beim Finden einer Lösung geht man von den Belegungen einiger Variablen aus die man sicher weiß und folgert weitere sichere Belegungen (via Propagation). Wenn nichts weiter sicher hergeleitet werden kann, dann wählt man einen Wahrheitswert einer Variable die noch offen ist. Stellt man dann fest, dass unsere Entscheidungen der Belegungen nicht zu einer Lösung führt, kann man Konfliktklauseln herleiten, welche ganze Bereiche eines Entscheidungsbaumes identifizieren, die nicht zu einer Lösung führen können. Also muss man sich nicht alle Belegungen anschauen, um eine Lösung zu finden. Diese Methode wird in der wissensbasierten KI (nicht also Maschine Learning) eingesetzt. Mit diesen Methoden können die NP-Probleme schneller gelöst werden und finden zB in der Schichtplanung, Konfiguration und vielen anderen Kombinatorischen Problemen Anwendung, sind aber im worst case immer noch exponentiell.

[renegranit]

Ich war eccht angekotzt von dem Thema, aber dein Video hat das Thema so interessant dargestellt, das ich mich damit noch viel mehr beschäftigt habe.

[HanzDavid]

Tiefe neuronale Netze scheinen zusammen mit den Problemgrößen tendenziell nur polynomiell zu wachsen (siehe beispielsweise Proteinfaltung oder Schach). Dabei konvergieren die Hochleistungsnetze gegen optimale Lösungen. Das legt nahe, dass P zumindest gegen NP konvergiert, da sich mit neuronalen Netzen Probleme angehen lassen, die in NP oder gar EXP liegen. Es ist also gut möglich, dass P nicht gleich NP gilt, aber vielleicht ist das an einem bestimmten Punkt garnicht mehr so wichtig wegen der Konvergenz. An einem bestimmten Punkt ist der Unterschied zwischen perfekt und fast perfekt in vielen Fällen nicht mehr sooo wichtig. Aber das kommt natürlich auf das Problem an, wenn es darum geht Verschlüsselungen zu knacken, wird fast perfekt zum Glück wahrscheinlich nicht reichen. :)

[reinerczerwinski]

Unter der Vorraussetzung, dass man NP-vollständige Probleme nicht wesentlich besser als mit Brute Force lösen kann, wurde bereits schon in den 90ern gezeigt, dass NP-vollständige Probleme mit Quantencomputern nicht effizient lösbar sind (BBBV-Theorem)

[UberBossPure]

Ich kann mir vorstellen, dass Ramanujan dieses Problem ganz nebenbei und zufällig bereits in seinem Kopf gelöst hat, aber mit einem anderem Axiom System.

[nosferatu]

Aber wenn P = NP mit experimentellen Möglichkeiten getestet wird, ersetzt das aber doch keinen rigerosen Beweis, das von dem mathematischen Institut ausgegeben wird.

[Adventure]

Probleme kann man niemals mit derselben Denkweise lösen, durch die sie entstanden sind.

[BELLAROSE]

P vs Np complete..
P does not equal NP

A^3 + B ^2 = C^3
Where A is 1/x of C
Or C multiplied by A equal 1.

Decision problem with complex values:
Problem: Given a set of complex numbers A, B, and x, is there a solution to the equation A^3 + B ^2 = C^3 where C is 1/x of A?
Decision question: does there exist a set of complex numbers A, B, and x, such that A^3 + B ^2= C^3, where C is 1/x of A.

To demonstrate NP-completeness, we need to show two things:
1. The problem is in NP: Given a potential solution, we can verify it in polynomial time.
2. The problem is NP-hard: Any problem in NP can be reduced to this problem in polynomial time.
To prove NP-hardness, we'll reduce the well-known NP-complete problem, the subset sum problem, to our decision problem with complex values.
Subset Sum Problem:
Given a set of integers and a target sum, does there exist a subset of the integers that sums to the target sum?
We can reduce the subset sum problem to our decision problem with complex values by transforming the integers into complex numbers with zero imaginary parts:
For each integer ai in the subset sum problem, we create a complex number.
Ai = ai +0i . We set B=0 and X=1
Now, if there exists a subset of integers that sums to the target sum, then there exists a solution to our decision problem with complex values, where A^3 +B^2 = C^3.
Therefore, our decision problem with complex values is NP-complete.

Solution is percise with no approximation.. does exist with the knowledge by this author of this post …

[dennismuller]

Ich habe eine Frage zum Punkt "es könnte sogar unmöglich sein, zu beweisen, dass P gleich oder ungleich NP ist" (12:47)

Ein Algorithmus, der ein NP-schweres Problem beweisbar effizient löst, wäre ja ein Beweis für P = NP. Wenn es also unmöglich ist, P vs NP zu lösen, dann kann es dementsprechend keinen solchen Algorithmus geben, woraus P =/= NP folgt.

Falls P vs NP also unlösbar ist, wäre diese Unlösbarkeit ebenfalls unmöglich zu beweisen, oder hab ich da jetzt einen Knoten in der Argumentation?

[rorallelich]

Hm... ich glaube, dass ich mich viel mit dieser Frage beschäftigt habe (allerdings "nur" praktische Anwendungsfälle von sehr komplexen Systemen; also keine Algorithmen). Meine beste Erklärung habe ich in der Philosophie gefunden.

Ich bin der Meinung, dass p!=np zutrifft. Das philosophische Abduktionsprinzip von Charles Sanders Pierce hat das Problem meiner Meinung nach gut beschrieben. Demnach sind es vor allem hypothetische Gründe die nur durch falsifizieren widerlegt oder andernfalls adäquat gesichert anzunehmen sind. Die Theorie wird vor allem mit wissenschaftlichen Fragefindungen und deren Gültigkeit in Verbindung gebracht. Allerdings habe ich den Eindruck, dass es grundsätzlich etwas mit komplexen Systemen zu tun hat.

(Im übrigen ist der Ansatz von Karl Popper ähnlich. In der Aussagenlogik oder Rechtsphilosophie ist dieses Problem ebenfalls bekannt um komplexe Schlussfolgerungen greifbar zu machen). Deduktion und Induktion sind dagegen reine Werkzeuge für die Beantwortung komplexer Fragen. In diesem Zusammenhang müsste man (fairerweise) mit jeder noch so krude-anmutenden Behauptung etwas unvoreingenommen umgegangen werden (was ja ki Systeme machen, so lange sie nicht gelenkt werden). Lenkung bedeutet langfristig Ordnung zu schaffen. Komplexität ist aber eine momentane Ordnung und deshalb komplex.

[zerocool]

Hört sich für mich nach der Frage an ist rot = grün .. nein ist es nicht, wenn es so wäre, dann gäbe es keine Farben. Allerdings würde jemand mit einer Rot-Grün-Blindheit immer behaupten rot = grün. 😉

Anders gesagt, es gibt leichte mathematische Probleme die sich beispielsweise in O(N) lösen lassen und eben andere Probleme mit O(N^2) oder sogar O(2^N) etc. Findet jemand einen effizienteren Algorithmus wird aus einem O(2^N) vielleicht ein O(N^2), aber dieser muss erst einmal "gefunden" werden und ob dieser überhaupt existiert ist ungewiss.

[btx]

Das Intro hat mich irgendwie stehen gelassen. Habe daher Chat GPT nach einer einfachen Erklärung des Problems gefragt:
"Das Problem lässt sich vereinfacht wie folgt darstellen: Wenn man eine Lösung für ein Problem in akzeptabler Zeit finden kann (P), kann man diese Lösung auch verifizieren oder überprüfen, ob sie korrekt ist, in ähnlich kurzer Zeit. Wenn es hingegen keine effiziente Methode gibt, eine Lösung zu finden (NP), könnte es dennoch eine effiziente Methode geben, um zu überprüfen, ob eine vorgeschlagene Lösung korrekt ist."

[weirdwordcombo]

Ich bin der Meinung dass gewisse Probleme nur mit einer gewissen Intelligenz gelöst werden können. Sobald wir super intelligente KI haben, die sicher min. noch 20 Jahre entfernt ist, wird sich sehr sehr viel lösen denke ich. Denn höhere Intelligenz macht Lösungen für harte Probleme offensichtlich.

[nosferatu]

Einfacher Beweis nehme an N=1
P = NP
P = 1×P
P = P
🤣

[Kappe]

immer wenn du von Problemen redest und ob/wie man diese effizient lösen kann, denk ich nur eins: 42

[sugandesenuds]

Ich frag einfach meinen Mathe Professor wie man das löst, der weiß alles...

[COCONUDD]

Simply ask q in Unis n schools w smart kids they ez wp prob