Wir haben über effiziente Algorithmen geschrieben, um komplexe Probleme zu lösen, wie den kürzesten Weg, den Euler-Graphen, den minimalen Spannbaum usw. Das waren alles Erfolgsgeschichten von Algorithmus-Designern. In diesem Beitrag werden Erfolgsgeschichten der Informatik diskutiert.
Können alle Rechenprobleme von einem Computer gelöst werden? Es gibt Rechenprobleme, die selbst mit unbegrenzter Zeit nicht durch Algorithmen gelöst werden können. Zum Beispiel Turing-Halteproblem (Bei einem Programm und einer Eingabe, ob das Programm schließlich angehalten wird, wenn es mit dieser Eingabe ausgeführt wird, oder für immer ausgeführt wird). Alan Turing hat bewiesen, dass ein allgemeiner Algorithmus zur Lösung des Halteproblems für alle möglichen Programmeingabepaare nicht existieren kann. Ein wichtiger Teil des Beweises ist, dass die Turing-Maschine als mathematische Definition eines Computers und eines Programms verwendet wurde (Quellenhalteproblem).
Status von NP Complete Probleme ist ein weiterer Fehler Geschichte, NP complete Probleme sind Probleme, deren Status unbekannt ist. Es wurde noch kein Polynomzeitalgorithmus für ein NP-vollständiges Problem entdeckt, noch konnte jemand beweisen, dass für keines von ihnen ein Polynomzeitalgorithmus existiert. Der interessante Teil ist, wenn eines der NP-vollständigen Probleme in Polynomzeit gelöst werden kann, dann können alle gelöst werden.
Was sind NP-, P-, NP-vollständige und NP-harte Probleme?
P ist eine Menge von Problemen, die durch eine deterministische Turing-Maschine in Polynomzeit gelöst werden können.NP ist eine Menge von Entscheidungsproblemen, die von einer nicht-deterministischen Turing-Maschine in Polynomzeit gelöst werden können. P ist eine Teilmenge von NP (jedes Problem, das von einer deterministischen Maschine in Polynomzeit gelöst werden kann, kann auch von einer nicht deterministischen Maschine in Polynomzeit gelöst werden).Informell ist NP eine Menge von Entscheidungsproblemen, die durch eine Polynomzeit über einen „Glücksalgorithmus“ gelöst werden können, einen magischen Algorithmus, der immer eine richtige Vermutung unter den gegebenen Entscheidungen trifft (Quelle Ref 1).
NP-vollständige Probleme sind die schwierigsten Probleme in der NP-Menge. Ein Entscheidungsproblem L ist NP-vollständig, wenn:
1) L ist in NP (Jede gegebene Lösung für NP-vollständige Probleme kann schnell verifiziert werden, aber es gibt keine effiziente bekannte Lösung).
2) Jedes Problem in NP ist in der Polynomzeit auf L reduzierbar (Reduktion ist unten definiert).
Ein Problem ist NP-schwer, wenn es der oben erwähnten Eigenschaft 2 folgt und nicht der Eigenschaft 1 folgen muss. Daher ist NP-Complete set auch eine Teilmenge von NP-Hard set.
Entscheidungs-vs. Optimierungsprobleme
NP-Vollständigkeit gilt für den Bereich der Entscheidungsprobleme. Es wurde auf diese Weise eingerichtet, weil es einfacher ist, die Schwierigkeit von Entscheidungsproblemen als die von Optimierungsproblemen zu vergleichen. In der Realität ermöglicht es uns jedoch häufig, ein Entscheidungsproblem in Polynomzeit zu lösen, um das entsprechende Optimierungsproblem in Polynomzeit zu lösen (unter Verwendung einer polynomischen Anzahl von Aufrufen des Entscheidungsproblems). Die Diskussion der Schwierigkeit von Entscheidungsproblemen entspricht also oft der Diskussion der Schwierigkeit von Optimierungsproblemen. (Quelle Ref 2).Betrachten Sie zum Beispiel das Vertex-Cover-Problem (Finden Sie bei einem Diagramm die minimale Größe des Vertex-Sets heraus, die alle Kanten abdeckt). Es ist ein Optimierungsproblem. Entsprechendes Entscheidungsproblem ist, gibt es bei ungerichtetem Graphen G und k eine Scheitelpunktabdeckung der Größe k?
Was ist Reduktion?
L1 und L2 seien zwei Entscheidungsprobleme. Angenommen, Algorithmus A2 löst L2. Das heißt, wenn y eine Eingabe für L2 ist, antwortet Algorithmus A2 mit Ja oder Nein, je nachdem, ob y zu L2 gehört oder nicht.
Die Idee ist, eine Transformation von L1 nach L2 zu finden, so dass der Algorithmus A2 Teil eines Algorithmus A1 sein kann, um L1 zu lösen.
Lernreduktion im Allgemeinen ist sehr wichtig. Wenn wir zum Beispiel Bibliotheksfunktionen haben, um ein bestimmtes Problem zu lösen, und wenn wir ein neues Problem auf eines der gelösten Probleme reduzieren können, sparen wir viel Zeit. Betrachten Sie das Beispiel eines Problems, bei dem wir den minimalen Produktpfad in einem gegebenen gerichteten Graphen finden müssen, wobei das Produkt des Pfades die Multiplikation der Gewichte der Kanten entlang des Pfades ist. Wenn wir Code für den Dijkstra-Algorithmus haben, um den kürzesten Pfad zu finden, können wir alle Gewichte protokollieren und den Dijkstra-Algorithmus verwenden, um den minimalen Produktpfad zu finden, anstatt einen neuen Code für dieses neue Problem zu schreiben.
Wie kann man beweisen, dass ein gegebenes Problem NP vollständig ist?Aus der Definition von NP-vollständig scheint es unmöglich zu beweisen, dass ein Problem L NP-vollständig ist. Per Definition müssen wir zeigen, dass jedes Problem in NP die Polynomzeit auf L reduzierbar ist. Die Idee ist, ein bekanntes NP-vollständiges Problem zu nehmen und es auf L zu reduzieren. Wenn eine Polynomzeitreduktion möglich ist, können wir beweisen, dass L NP-vollständig ist durch Transitivität der Reduktion (Wenn ein NP-vollständiges Problem in der Polynomzeit auf L reduzierbar ist, sind alle Probleme in der Polynomzeit auf L reduzierbar).
Was war das erste Problem, das als NP-Vollständig bewiesen wurde?Es muss ein erstes NP-vollständiges Problem geben, das durch Definition von NP-vollständigen Problemen bewiesen wurde. SAT (Boolean Satisfiability Problem) ist das erste NP-vollständige Problem, das von Cook bewiesen wurde (siehe CLRS-Buch zum Beweis).
Es ist immer nützlich, auch für Ingenieure über NP-Vollständigkeit Bescheid zu wissen. Angenommen, Sie werden gebeten, einen effizienten Algorithmus zu schreiben, um ein äußerst wichtiges Problem für Ihr Unternehmen zu lösen. Nach vielem Nachdenken können Sie nur einen exponentiellen Zeitansatz entwickeln, der unpraktisch ist. Wenn Sie nichts über NP-Vollständigkeit wissen, können Sie nur sagen, dass ich keinen effizienten Algorithmus finden konnte. Wenn Sie über NP-Vollständigkeit Bescheid wissen und beweisen, dass das Problem NP-vollständig ist, können Sie stolz sagen, dass die Polynomzeitlösung wahrscheinlich nicht existiert. Wenn eine Polynomzeitlösung möglich ist, löst diese Lösung ein großes Problem der Informatik, das viele Wissenschaftler seit Jahren versuchen.
Wir werden bald mehr NP-Vollständige Probleme und deren Beweis für NP-Vollständigkeit diskutieren.