P-NP-Problem

Erläuterungen

Wenn Sie z.B. ein Problem haben und jemand sagt: "Die Antwort auf Ihr Problem ist die Menge der Zahlen 1, 2, 3, 4, 5", kann ein Computer vielleicht schnell herausfinden, ob die Antwort richtig oder falsch ist, aber es kann sehr lange dauern, bis der Computer tatsächlich von selbst auf "1, 2, 3, 4, 5" kommt. Ein weiteres Beispiel ist das Finden von Primzahlen. Es ist leicht zu überprüfen, ob eine Zahl eine Primzahl ist, aber es ist sehr schwierig, diese Zahlen überhaupt zu finden. Für einige interessante, praktische Fragen dieser Art fehlt uns jede Möglichkeit, schnell eine Antwort zu finden, aber wenn uns eine Antwort gegeben wird, ist es möglich, die Antwort schnell zu überprüfen, d.h. zu verifizieren. Auf diese Weise kann man sich NP-Probleme wie Rätsel vorstellen: Es mag schwierig sein, die Antwort auf ein Rätsel zu finden, aber wenn man die Antwort einmal gehört hat, scheint die Antwort offensichtlich zu sein. In diesem Vergleich (Analogie) lautet die Grundfrage: Sind Rätsel wirklich so schwer, wie wir denken, dass sie es sind, oder fehlt uns etwas?

Weil diese Art von P-gegen-NP-Fragen so praktisch wichtig sind, wollen viele Mathematiker, Wissenschaftler und Computerprogrammierer die allgemeine Behauptung beweisen, dass jedes schnell überprüfte Problem auch schnell gelöst werden kann. Diese Frage ist wichtig genug, dass das Clay Mathematical Institute jedem, der erfolgreich einen Beweis oder eine gültige Erklärung liefert, die diese widerlegt, 1.000.000 Dollar gibt.

Wenn wir etwas tiefer graben, stellen wir fest, dass alle P-Probleme NP-Probleme sind: Es ist leicht zu überprüfen, ob eine Lösung richtig ist, indem man das Problem löst und die beiden Lösungen vergleicht. Die Leute wollen jedoch das Gegenteil wissen: Gibt es noch andere NP-Probleme als P-Probleme, oder sind alle NP-Probleme nur P-Probleme? Wenn NP-Probleme wirklich nicht dasselbe sind wie P-Probleme (P ≠ NP), würde das bedeuten, dass es keine generellen, schnellen Wege zur Lösung dieser NP-Probleme geben kann, egal wie sehr wir suchen. Wenn jedoch alle NP-Probleme P-Probleme sind (P = NP), würde das bedeuten, dass es neue, sehr schnelle Methoden zur Problemlösung gibt. Wir haben sie nur noch nicht gefunden.

Da die besten Bemühungen von Wissenschaftlern und Mathematikern noch keine allgemeinen, einfachen Methoden zur Lösung von NP-Problemen gefunden haben, glauben viele Menschen, dass es andere NP-Probleme als P-Probleme gibt (d.h. dass P ≠ NP wahr ist). Die meisten Mathematiker glauben dies auch, aber derzeit hat es noch niemand durch rigorose mathematische Analyse bewiesen. Wenn nachgewiesen werden kann, dass NP und P gleich sind (P = NP ist wahr), hätte dies einen enormen Einfluss auf viele Aspekte des täglichen Lebens. Aus diesem Grund ist die Frage P versus NP ein wichtiges und weithin untersuchtes Thema.

Beispiel

Angenommen, jemand will zwei Türme bauen, indem er Felsen unterschiedlicher Masse stapelt. Man möchte sicherstellen, dass jeder der Türme genau die gleiche Masse hat. Das bedeutet, dass man die Steine in zwei Haufen legen muss, die die gleiche Masse haben. Wenn man eine Teilung der Steine errät, von der man glaubt, dass sie funktioniert, könnte man leicht überprüfen, ob man Recht hat. (Um die Antwort zu überprüfen, kann man die Steine in zwei Haufen teilen und dann mit einer Waage prüfen, ob sie die gleiche Masse haben). Weil es einfach ist, dieses Problem, das von Informatikern "Partition" genannt wird, zu überprüfen - einfacher, als es direkt zu lösen, wie wir sehen werden -, ist es kein P-Problem. ^[]

Wie schwierig ist es, das Problem zu lösen, ohne Umschweife? Wenn man mit nur 100 Steinen beginnt, gibt es 2^{100-1}-1 = 633,825,300,114,114,700,748,351,602,687, oder etwa 6.3 x 10^{29} mögliche Wege (Kombinationen), diese Steine in zwei Haufen zu teilen. Wenn man jeden Tag eine einzigartige Kombination von Gesteinen prüfen könnte, würde dies 1,3 x 10^{22} oder 1.300.000.000.000.000.000.000.000 Jahre Anstrengung erfordern. Zum Vergleich: Physiker gehen davon aus, dass das Universum etwa 1,4 x 10^{10} Jahre alt ist (450.000.000.000.000.000.000 oder etwa 4,5 x 10^{17} Sekunden oder etwa ein Billionstel so alt wie die Zeit, die wir für unsere Gesteinsstapelarbeiten benötigen würden. Das bedeutet, dass man, wenn man sich die gesamte Zeit nimmt, die seit dem Beginn des Universums vergangen ist, jede Sekunde mehr als zwei Billionen (2.000.000.000.000.000) verschiedene Arten der Gesteinsteilung prüfen müsste, um all die verschiedenen Arten zu überprüfen.

Würde man einen leistungsfähigen Computer programmieren, um all diese Arten der Gesteinsaufteilung zu testen, könnte man mit den heutigen Systemen 1.000.000 Kombinationen pro Sekunde überprüfen. Das bedeutet, man bräuchte immer noch 2.000.000 sehr leistungsstarke Computer, die seit der Entstehung des Universums arbeiten, um alle Arten der Gesteinsaufteilung zu testen.

Es könnte jedoch möglich sein, eine Methode zu finden, um die Felsen in zwei gleiche Haufen zu teilen, ohne alle Kombinationen zu prüfen. Die Frage "Ist P gleich NP?" ist eine Kurzform für die Frage, ob es eine solche Methode geben kann.

Warum es wichtig ist

Es gibt viele wichtige NP-Probleme, von denen die Menschen nicht wissen, wie sie sie schneller lösen können, als jede mögliche Antwort zu testen. Hier sind einige Beispiele:

• Ein Handelsreisender möchte 100 Städte besuchen, indem er mit dem Auto fährt und seine Reise zu Hause beginnt und beendet. Er hat einen begrenzten Vorrat an Benzin, so dass er insgesamt nur 10.000 Kilometer fahren kann. Er möchte wissen, ob er alle Städte besuchen kann, ohne dass ihm das Benzin ausgeht.
• Eine Schule bietet 100 verschiedene Klassen an, und ein Lehrer muss für jede Klasse eine Stunde für die Abschlussprüfung wählen. Um Betrug zu verhindern, müssen alle Schüler, die an einer Klasse teilnehmen, die Prüfung für diese Klasse zur gleichen Zeit ablegen. Wenn ein Student mehr als eine Klasse besucht, müssen alle diese Prüfungen zu einer anderen Zeit stattfinden. Der Lehrer möchte wissen, ob er alle Prüfungen am selben Tag einplanen kann, so dass jeder Student die Prüfung für jede seiner Klassen ablegen kann.
• Ein Landwirt will 100 Wassermelonen verschiedener Massen auf den Markt bringen. Sie muss die Wassermelonen in Kisten verpacken. Jede Kiste fasst ohne Bruch nur 20 Kilogramm. Der Landwirt muss wissen, ob 10 Kisten ausreichen, um alle 100 Wassermelonen auf den Markt zu bringen. (Das ist trivial, wenn nicht mehr als eine Wassermelone mehr als 2 kg wiegt, dann können in jede der Kisten 10 beliebige Wassermelonen gelegt werden, wenn nicht mehr als zehn Wassermelonen mehr als 2 kg wiegen, dann kann in jede Kiste eine von ihnen gelegt werden, usw., um eine schnelle Lösung zu finden; Beobachtung wird der Schlüssel zu jeder schnellen Lösung wie dieser oder dem Problem der Zahlensätze sein).
• Eine große Kunstgalerie hat viele Räume, und jede Wand ist mit vielen teuren Gemälden bedeckt. Der Besitzer der Galerie möchte Kameras kaufen, um diese Gemälde zu beobachten, für den Fall, dass ein Dieb versucht, eines von ihnen zu stehlen. Er möchte wissen, ob ihm 100 Kameras ausreichen, um sicherzustellen, dass jedes Gemälde von mindestens einer Kamera gesehen werden kann.
• Das Cliquenproblem: Der Direktor einer Schule hat eine Liste, auf der die Schülerinnen und Schüler miteinander befreundet sind. Sie möchte eine Gruppe von 10% der Schülerinnen und Schüler finden, die alle miteinander befreundet sind.

Exponentielle Zeit

Im obigen Beispiel sehen wir, dass es bei 100 {\Displaystyle 100} Felsen 2 100 {\Displaystyle 2^{100}}} Möglichkeiten gibt, die Menge der Felsen zu partitionieren. Bei n {\Darstellungsstil n} Felsen gibt es 2 n {\Darstellungsstil 2^{n}} Kombinationen. Die Funktion f ( n ) = 2 n {\darstellungsstil f(n)=2^{n}} ist eine Exponentialfunktion. Sie ist wichtig für NP, weil sie die Anzahl der Berechnungen modelliert, die im schlimmsten Fall zur Lösung eines Problems erforderlich sind, und damit auch die Zeit, die im schlimmsten Fall benötigt wird.

Und bisher haben die Lösungen für die schwierigen Probleme in der Größenordnung von 2 n {\darstellungsstil 2^{n}} Berechnungen erfordert. Für jedes spezielle Problem hat man Wege gefunden, die Anzahl der erforderlichen Berechnungen zu reduzieren. Man könnte herausfinden, dass eine Möglichkeit, nur 1 % der schlimmstmöglichen Anzahl von Berechnungen durchzuführen, eine Menge Rechenzeit einspart, aber das sind immer noch 0,01 × ( 2 n ) {\darstellungsstil0,01\mal (2^{n})}Berechnungen. Und jeder zusätzliche Felsen verdoppelt immer noch die Anzahl der Berechnungen, die zur Lösung des Problems erforderlich sind. Es gibt Erkenntnisse, die Methoden hervorbringen können, mit denen noch weniger Berechnungen durchgeführt werden können, die Variationen des Modells erzeugen: z.B. 2 n / n 3 {\Darstellungsstil 2^{n}/n^{3}}} . Aber die Exponentialfunktion dominiert auch dann noch, wenn n {\Darstellungsstil n} wächst.

Betrachten Sie das Problem der Prüfungsplanung (oben beschrieben). Aber nehmen wir als nächstes an, dass es 15000 Studenten gibt. Es gibt ein Computerprogramm, das die Stundenpläne aller 15000 Studenten aufnimmt. Es läuft in einer Stunde und gibt einen Prüfungsplan aus, so dass alle Studenten ihre Prüfungen in einer Woche absolvieren können. Es erfüllt viele Regeln (keine Back-to-Back-Prüfungen, nicht mehr als 2 Prüfungen in einer 28-Stunden-Periode, ...), um den Stress der Prüfungswoche zu begrenzen. Das Programm läuft eine Stunde in der Halbzeitpause und jeder kennt seinen Prüfungsplan mit viel Zeit zur Vorbereitung.

Im nächsten Jahr gibt es jedoch 10 weitere Studenten. Wenn das gleiche Programm auf dem gleichen Computer läuft, dann wird aus dieser einen Stunde 2 10 {\Displaystyle 2^{10}} Stunden, weil jeder weitere Student die Berechnungen verdoppelt. Das sind 6 {\Anzeigestil 6} Wochen! Wenn es 20 weitere Studierende gäbe, dann

2 20 {\darstellungsstil 2^{20}} Stunden = 1048576 {\darstellungsstil 1048576} Stunden ~ 43691 {\darstellungsstil 43691} Tage ~ 113 {\darstellungsstil 113} Jahre

Für 15000 Schülerinnen und Schüler dauert es also eine Stunde. Für 15020 Schülerinnen und Schüler mit dem Display-Stil 15020dauert es 113 Jahre.

Wie Sie sehen können, wachsen Exponentialfunktionen sehr schnell. Die meisten Mathematiker glauben, dass die schwierigsten NP-Probleme exponentielle Zeit zur Lösung benötigen.

NP-vollständige Probleme

Mathematiker können zeigen, dass es einige NP-Probleme gibt, die NP-vollständig sind. Ein NP-komplettes Problem ist mindestens genauso schwierig zu lösen wie jedes andere NP-Problem. Das heißt, wenn jemand eine Methode gefunden hat, um ein NP-vollständiges Problem schnell zu lösen, könnte er dieselbe Methode verwenden, um jedes NP-Problem schnell zu lösen. Alle oben aufgeführten Probleme sind NP-komplett. Wenn der Verkäufer also eine Möglichkeit gefunden hat, seine Reise schnell zu planen, könnte er dies der Lehrkraft mitteilen, und sie könnte dieselbe Methode zur Planung der Prüfungen verwenden. Der Landwirt könnte mit der gleichen Methode feststellen, wie viele Kisten sie braucht, und die Frau könnte mit der gleichen Methode einen Weg finden, ihre Türme zu bauen.

Da eine Methode, die eines dieser Probleme schnell löst, alle Probleme lösen kann, gibt es viele Menschen, die eines finden wollen. Da es jedoch so viele verschiedene NP-Komplett-Probleme gibt und bisher niemand einen Weg gefunden hat, auch nur eines davon schnell zu lösen, glauben die meisten Experten, dass eine schnelle Lösung von NP-Komplett-Problemen nicht möglich ist.

Grundlegende Eigenschaften

In der rechnerischen Komplexitätstheorie ist die Komplexitätsklasse NP-vollständig (abgekürzt NP-C oder NPC) eine Klasse von Problemen mit zwei Eigenschaften:

• Sie gehört zur Problematik der NP (nicht-deterministische Polynomzeit): Jede gegebene Lösung des Problems kann schnell verifiziert werden (in polynomialer Zeit).
• Es gehört auch zu den NP-harten Problemen: Diejenigen, die mindestens so hart sind wie die härtesten Probleme in NP. Probleme, die NP-hart sind, müssen keine Elemente von NP sein; ja, sie sind vielleicht nicht einmal entscheidbar.

Formaler Überblick

NP-vollständig ist eine Teilmenge von NP, der Menge aller Entscheidungsprobleme, deren Lösungen in polynomialer Zeit verifiziert werden können; NP kann äquivalent als die Menge von Entscheidungsproblemen definiert werden, die in polynomialer Zeit auf einer Maschine gelöst werden. Ein Problem p in NP ist auch in NPC, wenn und nur wenn jedes andere Problem in NP in p in Polynomzeit transformiert wird. NP-vollständig sollte als Adjektiv verwendet werden: Probleme in der Klasse NP-vollständig waren als NP+vollständige Probleme.

NP-komplette Probleme werden untersucht, weil die Fähigkeit, Lösungen für ein Problem schnell zu überprüfen (NP) mit der Fähigkeit, ein Problem schnell zu lösen (P), zu korrelieren scheint. Es wird festgestellt, dass jedes Problem in NP schnell gelöst wird - als P = NP: Problemsatz bezeichnet. Das einzelne Problem in NP-vollständig wird schnell gelöst, schneller als jedes Problem in NP ebenfalls schnell gelöst wird, weil die Definition eines NP-vollständigen Problems besagt, dass jedes Problem in NP schnell auf jedes Problem in NP-vollständig reduzierbar sein muss (es wird in der Polynomzeit reduziert). [1]

Beispiele

Das Boolesche Erfüllbarkeitsproblem ist bekanntermaßen NP-vollständig. 1972 formulierte Richard Karp 21 Probleme, von denen bekannt ist, dass sie NP-vollständig sind. Diese sind als Karps 21 NP-vollständige Probleme bekannt. Dazu gehören Probleme wie das ganzzahlige Programmierproblem, das lineare Programmiertechniken auf die ganzen Zahlen anwendet, das Rucksackproblem oder das Vertex-Cover-Problem.