Was ist eine NP-Vollendung in der Informatik?

Question

Was ist ein NP-komplettes Problem? Warum ist es ein so wichtiges Thema in der Informatik?

Answer 1

Es handelt sich um eine Klasse von Problemen, bei denen wir alle Möglichkeiten simulieren müssen, um sicher zu sein, dass wir die optimale Lösung haben.

Es gibt eine Menge guter Heuristiken für einige NP-komplette Probleme, aber sie sind bestenfalls eine fundierte Vermutung.

Answer 2

Wenn Sie nach einem Beispiel für ein NP-komplettes Problem suchen, dann schlage ich vor, dass Sie einen Blick auf folgende Seite werfen 3-SAT .

Die Grundvoraussetzung ist, dass Sie einen Ausdruck in konjunktive Normalform Das ist eine Art zu sagen, dass man eine Reihe von Ausdrücken hat, die durch ODERs verbunden sind und alle wahr sein müssen:

(a or b) and (b or !c) and (d or !e or f) ...

Das 3-SAT-Problem besteht darin, eine Lösung zu finden, die den Ausdruck erfüllt, bei dem jeder der ODER-Ausdrücke genau 3 Boolesche Übereinstimmungen hat:

(a or !b or !c) and (!a or b or !d) and (b or !c or d) ...

Eine Lösung für diese Frage könnte lauten (a=T, b=T, c=F, d=F). Es wurde jedoch noch kein Algorithmus entdeckt, der dieses Problem im allgemeinen Fall in polynomialer Zeit lösen kann. Das bedeutet, dass der beste Weg, dieses Problem zu lösen, im Wesentlichen darin besteht, mit roher Gewalt zu raten und verschiedene Kombinationen auszuprobieren, bis man eine findet, die funktioniert.

Das Besondere am 3-SAT-Problem ist, dass JEDES NP-komplette Problem auf ein 3-SAT-Problem reduziert werden kann. Das bedeutet, dass man, wenn man einen Polynomialzeit-Algorithmus zur Lösung dieses Problems finden kann, Folgendes erhält $1,000,000 ganz zu schweigen von dem Respekt und der Bewunderung der Informatiker und Mathematiker in aller Welt.

Answer 3

Ganz ehrlich, Wikipedia könnte der beste Ort sein, um nach einer Antwort auf diese Frage zu suchen.

Wenn NP = P ist, dann können wir sehr schwierige Probleme viel schneller lösen, als wir es bisher für möglich hielten. Wenn wir nur ein NP-komplettes Problem in P (polynomieller) Zeit lösen, dann kann es auf alle anderen Probleme der Kategorie NP-komplett angewendet werden.

Answer 4

Wir müssen Algorithmen und Probleme trennen. Wir schreiben Algorithmen, um Probleme zu lösen, und sie skalieren auf eine bestimmte Weise. Auch wenn dies eine Vereinfachung ist, sollten wir einen Algorithmus mit "P" kennzeichnen, wenn die Skalierung gut genug ist, und mit "NP", wenn sie es nicht ist.

Es ist hilfreich, etwas über die Probleme zu wissen, die wir zu lösen versuchen, und nicht über die Algorithmen, mit denen wir sie lösen. Wir werden also sagen, dass alle Probleme, für die es einen gut skalierenden Algorithmus gibt, "in P" sind. Und diejenigen, die einen schlecht skalierenden Algorithmus haben, sind "in NP".

Das bedeutet, dass viele einfache Probleme auch "in NP" sind, weil wir schlechte Algorithmen schreiben können, um einfache Probleme zu lösen. Es wäre gut zu wissen, welche Probleme in NP die wirklich kniffligen sind, aber wir wollen nicht einfach sagen "es sind die, für die wir keinen guten Algorithmus gefunden haben". Schließlich könnte ich mir ein Problem ausdenken (nennen wir es X), von dem ich denke, dass es einen supertollen Algorithmus braucht. Ich erzähle der Welt, dass der beste Algorithmus, den ich zur Lösung von X finden konnte, schlecht skaliert, und deshalb denke ich, dass X ein wirklich schwieriges Problem ist. Aber vielleicht erfindet morgen jemand, der schlauer ist als ich, einen Algorithmus, der X löst und in P ist. Das ist also keine sehr gute Definition von schwierigen Problemen.

Trotzdem gibt es viele NP-Probleme, für die niemand einen guten Algorithmus kennt. Wenn ich also beweisen dass X eine bestimmte Art von Problem ist: ein Problem, bei dem ein guter Algorithmus zur Lösung von X también auf Umwegen zu einem guten Algorithmus für jede anderes Problem in NP. Nun, jetzt sind die Leute vielleicht ein bisschen mehr davon überzeugt, dass X ein wirklich kniffliges Problem ist. Und in diesem Fall nennen wir X NP-komplett.

Answer 5

Ich habe eine Erklärung gehört, die lautet:" NP-Vollständigkeit ist wahrscheinlich eine der rätselhaftesten Ideen im Studium der Algorithmen. "NP" steht für "nicht-deterministische polynomielle Zeit" und ist der Name für eine so genannte Komplexitätsklasse, zu der Probleme gehören können. Das Wichtigste am Begriff NP Komplexitätsklasse ist, dass Probleme innerhalb dieser Klasse verifiziert durch einen Polynomialzeit-Algorithmus. Betrachten wir als Beispiel das Problem des Zählens von Dingen. Angenommen, auf einem Tisch liegt ein Haufen Äpfel. Das Problem lautet: "Wie viele Äpfel sind es?" Sie erhalten eine mögliche Antwort, nämlich 8. Sie können diese Antwort in polynomialer Zeit überprüfen, indem Sie den Algorithmus zum Zählen der Äpfel verwenden. Das Zählen der Äpfel geschieht in O(n)-Zeit (das ist die Big-Oh-Schreibweise), denn es dauert einen Schritt, um jeden Apfel zu zählen. Für n Äpfel braucht man also n Schritte. Dieses Problem fällt in die NP-Komplexitätsklasse.

Ein Problem wird klassifiziert als NP-komplett wenn nachgewiesen werden kann, dass es sich sowohl NP-Hard y nachprüfbar in polynomieller Zeit. Ohne zu sehr in die Diskussion über NP-Hard einzutreten, genügt es zu sagen, dass es bestimmte Probleme gibt, für die keine Lösungen in polynomieller Zeit gefunden wurden. Das heißt, man braucht etwa n! (n-fache) Schritte, um sie zu lösen. Wenn man jedoch eine Lösung für ein NP-komplettes Problem erhält, kann man sie in Polynomialzeit überprüfen.

Ein klassisches Beispiel für ein NP-vollständiges Problem ist das Traveling Salesman Problem".

Der Autor: ApoxyButt Von: http://www.everything2.com/title/NP-complete