Die im Alter P-versus-NP-Problem
Also, was ist dann das P-versus-NP-problem?
Für den Datensatz ist der Status quo der P≠NP.
P (Polynomzeit) bezieht sich auf die Klasse von Problemen, die durch einen Algorithmus in Polynomzeit gelöst werden können. Probleme in der P-Klasse können von so einfachen Dingen wie der Multiplikation bis zum Finden der größten Zahl in einer Liste reichen. Sie sind die relativ „einfacheren“ Probleme.
NP (non-deterministic polynomial time) bezieht sich auf die Klasse von Problemen, die in polynomialer Zeit von einem nicht-deterministischen Computer gelöst werden können., Dies ist im Wesentlichen eine andere Art zu sagen: „Wenn ich unbegrenzte Rechenleistung habe (dh so viele Computer, wie ich brauche), kann ich jedes Problem in höchstens polynomialer Zeit lösen“. Intuitiver bezieht es sich jedoch auf die Klasse von Problemen, die derzeit keine Möglichkeit haben, eine schnelle (Polynomzeit) Antwort zu finden, kann ABER schnell verifiziert werden (in Polynomzeit), wenn man die Lösung für das Problem bereitstellt. Der hier verifizierte Begriff bedeutet, dass man überprüfen kann, ob die bereitgestellte Lösung tatsächlich korrekt ist.
Klar, basierend auf der obigen Definition, P ⊆ NP., Schauen wir uns ein Beispiel an, um dieses abstrakte Problem zu veranschaulichen.
Eines der häufigsten und dennoch effektivsten Beispiele ist Sudoku. Bei einem ungelösten Sudoku-Raster (z. B. 9 x 9) würde es einen Algorithmus ziemlich lange dauern, bis er eines gelöst hat. Wenn das 9 x 9-Raster jedoch auf ein 100 x 100-oder 10,000 x 10,000-Raster ansteigt, würde die Zeit, die zur Lösung benötigt wird, exponentiell zunehmen, da das Problem selbst erheblich schwieriger wird., Angesichts eines gelösten Sudoku-Rasters (von 9 x 9) ist es jedoch ziemlich einfach zu überprüfen, ob die jeweilige Lösung tatsächlich korrekt ist, selbst wenn die Größe auf 10.000 mal 10.000 skaliert wird. Es wäre langsamer, aber die Zeit zum Überprüfen einer Lösung steigt langsamer (polynomisch).
Es gibt viele andere NP-Probleme, einschließlich des Rucksackproblems und des Problems der reisenden Verkäufer, und sie sind insofern ähnlich, als sie schwer zu lösen, aber schnell zu überprüfen sind., Das grundlegende Problem, das wir hier zu lösen versuchen, ist:
Bedeutet die schnelle Erkennung der richtigen Antworten, dass es auch einen schnellen Weg gibt, sie zu finden?
Wenn ja (dh P=NP), könnte dies die Sichtweise auf diese NP-Probleme erheblich ändern, da dies bedeutet, dass es einen schnellen Weg gibt, all diese Probleme zu lösen, nur dass wir noch nicht herausfinden konnten, wie.
Wenn dies nicht kompliziert genug ist, lassen Sie es uns aufpeppen.,
Unter diesen NP-Problemen gibt es einen König aller Probleme, die Forscher NP-Complete-Probleme nennen. Formal handelt es sich um eine Reihe von Problemen, auf die jedes andere NP-Problem in Polynomzeit reduziert (unten angesprochen) werden kann und deren Lösung in Polynomzeit noch verifiziert werden kann. Dies bedeutet, dass jedes NP-Problem in ein NP-vollständiges Problem umgewandelt werden kann.
Informell sind sie die „härtesten“ der NP-Probleme., Wenn also ein NP-vollständiges Problem in Polynomzeit gelöst werden kann, kann jedes NP-vollständige Problem in Polynomzeit gelöst werden, und jedes Problem in NP kann in Polynomzeit gelöst werden (dh P=NP). Das bekannteste Beispiel wäre das Problem der reisenden Verkäufer.
gibt es auch eine Reihe von Problemen, die als NP-Hard-Probleme bezeichnet werden., Diese Probleme sind mindestens so schwer wie NP-Probleme, jedoch ohne die Bedingung, dass sie in polynomialer Zeit gelöst werden müssen. Dies deutet darauf hin, dass NP-Hard-Probleme möglicherweise nicht unbedingt Teil der NP-Klasse sind. Ein Beispiel wäre das Lösen eines Schachbretts — angesichts eines Zustands eines Schachbretts ist es fast unmöglich zu sagen, ob ein bestimmter Zug im gegebenen Zustand tatsächlich der optimale Zug ist. Formal gibt es keinen Polynomzeitalgorithmus, um eine Lösung für ein NP-Hard-Problem zu überprüfen.,
Wenn wir die beiden zusammenfügen, bedeutet ein NP-vollständiges Problem, dass es NP-hart ist, aber ein NP-hartes Problem impliziert NICHT, dass es NP-vollständig ist.
Definieren der NP-Vollständigkeit
Ein Problem L, ist NP-vollständig wenn:
- L ist NP-Schwer
- L gehört zu NP
Das folgende Diagramm (Fokus auf der linken Seite) sollte die Dinge klarer machen.,
Wait, what does it mean by reducing A to B?
Reduction forms the crux of NP-Completeness.,
Informell kann ein Problem L1 auf ein anderes Problem L2 reduziert werden, wenn:
- Jede Instanz von L1 als Instanz von L2 modelliert werden kann
- Die Lösung für letzteres bietet eine Lösung für das erstere und umgekehrt
Um dies intuitiv zu verstehen, kann man es sich so vorstellen:
Wenn L1 auf L2 reduzierbar ist, muss L1 HÖCHSTENS so hart wie L2. Umgekehrt muss L2 MINDESTENS so hart sein wie L1.
Mathematisch wird dies bezeichnet als: L1 ≤p L2 (gelesen als“L1 ist polynom auf L2 reduzierbar“).,
