P vs. NP: The MILLION Dollar PROBLEM of Computer Science
HTML-код
- Опубликовано: 30 июл 2024
- One of the most important and oldest questions in computer science is the so-called "P vs NP" problem.
Learn computer science for free on my website: bootstrap.academy/
*Chapter:
00:00 Introduction
04:33 Implications of the P / NP Problem
6:58 Techniques for proving P / NP
10:30 Current state of research
13:05 Conclusion
* All my social media portals *:
bio.link/themorpheus
Discord:
the-morpheus.de/discord.html
Support Me - Thank You!:
www.patreon.com/user?u=5322110
www.paypal.me/TheMorpheus
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.
Das trifft es richtig gut
Zitat stammt von Scott Aaronson
@@reinerczerwinski1326 Hab ich doch geschrieben??
@@AmagoThePlayer Stimmt, brauche ne Brille
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.
5:00 Es kann sein, das P ungleich NP ist, aber Faktorisierung schnell lösbar ist, da Fakorisierung höchstwahrscheinlich nicht NP-schwer ist
Super Video!
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.
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.
Aber wenn P = NP mit experimentellen Möglichkeiten getestet wird, ersetzt das aber doch keinen rigerosen Beweis, das von dem mathematischen Institut ausgegeben wird.
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. :)
Nein, unter der Annahme P != NP, kann einfach gezeigt werden, dass es für manche Probleme keine guten Approximationen gibt, wie das TSP, also "konvergiert" das auch nicht gegen eine optimale Lösung
@@Simon-qn1ug Hallo Simon,
wenn Du beweisen kannst, dass es für das TSP keine effiziente Lösung gibt, dann hast Du das millenium Problem gelöst, dann wäre nämlich bewiesen, dass P != NP gilt. Hol Dir den Gewinn! ;)
Darüberhinaus hat die Optimalität einer Lösung nichts mit ihrer Laufzeit zu tun. Und natürlich gibt es für das TSP strategien, um das Finden einer optimalen Lösung effizienter zu machen. Die Frage ist nur, ob es auch eine Strategie gibt damit Polynomiallaufzeit im Worst-Case garantieren zu können. Wie ich beschrieben hatte, schaffen es neuronale Netze Annäherungen an Problemlösungen zu erzeugen, sie Lösen es aber nicht Optimal sondern nur gut, dennoch ist es auffällig, wie sie trotz ihrer nur polynomialen Laufzeit so gute Annäherungen an optimale Lösungen erreichen können.
Wenn Du mathmathisch beweisen kannst, dass keine Strategie zur garantiert optimalen Lösung des TSP in polynomiallaufzeit existiert, dann hast Du die P != NP Annahme erfolgreich bewiesen. Wenn Du das Gegenteil beweisen kannst, hast Du die Annahme P != NP erfolgreich wiederlegt. Bis dahin macht es in diesem Kontext keinen Sinn irgendetwas unter der Annahme P != NP zu Zeigen, weil wir ja garnicht wissen, ob die Annahme wahr oder falsch ist. Es sei denn, diese Annahme dient der mathematischen Beweisführung selbst. :)
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)
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.
Der Typ war wahrlich faszinierend
Ramanujan war da schon tot
Hübsches Architects Tourshirt
Probleme kann man niemals mit derselben Denkweise lösen, durch die sie entstanden sind.
Meiste Zitate die Einstein zugeschrieben werden hat er nie wirklich gesagt
Kann mir jmd sagen ob das Zitat true ist am besten mit Quelle. (Wäre sehr hilfreich)
Ich denke Deine Aussage ist nicht allgemeingültig Adventure1844: Wenn Du immer wieder auf ein Holzbrett einschlägst, kann das Problem entstehen, dass sich deine Hand verletzt. Wenn Du weiter auf das Brett einschlägst, kann es passieren, dass das Brett zeurst nachgibt, was zu der Möglichkeit führt, dass die Verletzung wieder mit der Zeit verschwinden kann.
Anderes Beispiel: Du erhitzt Wasser, ab einer bestimmten Temperatur entsteht das Problem, dass sich darin sehr leicht Bakterien vermehren können. Du kannst dieses Problem aber durch weitere Erhitzung lösen. Die Aussage scheint auf solche Probleme nicht zuzutreffen, bei dem das Problem zwischen zwei extremen besteht und Du durch eine Strategie vom einem Extrem in die problematische Mitte rückst, aber durch das fortsetzen der selben Strategie in das lösende andere Extrem gleitest.
@@flockyyy9763 Das Zitat scheint nicht immer zuzutreffen, (siehe oben) :)
Wir haben erst ein Problem wenn jemand danach fragt also frag nicht.
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.
Einfacher Beweis nehme an N=1
P = NP
P = 1×P
P = P
🤣
Gebt diesem Mann den Nobelpreis!
Ich mein, ja, aber auch irgendwie nein
heißt aber auch das für alle N ungleich 1 P ungleich NP ist
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.
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 …
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.
immer wenn du von Problemen redest und ob/wie man diese effizient lösen kann, denk ich nur eins: 42
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."
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?
Simply ask q in Unis n schools w smart kids they ez wp prob
Ich frag einfach meinen Mathe Professor wie man das löst, der weiß alles...
Sag mir bitte die Antwort dann 😂
@@TheMorpheusTutorials ne, die kohle sack ich ein
ich habe einen Psychologen mit der Lösung meiner Probleme beauftragt.
No proo