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

Soweit ich das verstanden habe

P ist die Menge der Probleme, die in polynomieller Zeit mit einem deterministischen TM gelöst werden können.

NP ist die Menge der Probleme, bei denen ein nicht-deterministischer TM in polynomieller Zeit gelöst werden muss. Das bedeutet, dass wir alle verschiedenen Kombinationen von Variablen parallel prüfen können, wobei jede Instanz Polynomialzeit benötigt. Wenn das Problem lösbar ist, dann würde mindestens eine dieser parallelen Instanzen von TM mit "ja" aufhören. Das bedeutet auch, dass man, wenn man eine korrekte Vermutung über die Variablen/Lösung hat, diese nur noch in Polynomialzeit auf ihre Gültigkeit überprüfen muss.

NP-Hard ist die Menge der Probleme, die schwieriger als NP sind. Das bedeutet, dass NP-Hard-Probleme schwieriger sind als jedes Problem in der NP-Menge. Diese Probleme sind exponentiell, selbst wenn man den Nicht-Determinismus von Turing-Maschinen verwendet. Parallele Berechnungen sind also bei der Lösung dieser Probleme nicht hilfreich.

NP-Complete ist die Schnittmenge von NP und NP-Hard. Nach dem, was ich verstanden habe,

1. Probleme in NP-Complete sind mindestens so schwer wie das härteste Problem in der NP-Menge.
2. Die Klasse aller NP-vollständigen Probleme ist äquivalent zueinander, d.h. ein Problem der NP-vollständigen Menge kann auf jedes andere NP-vollständige Problem reduziert werden. Das heißt, wenn eines der NP-vollständigen Probleme eine effiziente Lösung hätte, dann könnten alle NP-vollständigen Probleme mit derselben Lösung gelöst werden.

Wenn ein beliebiges Problem der NP-Vollständigen Menge deterministisch in Polynomialzeit lösbar ist, dann ist die gesamte NP-Vollständige Menge deterministisch in Polynomialzeit lösbar. Da NP-vollständige Probleme mindestens so schwer sind wie das härteste Problem in der NP-Menge, werden alle Probleme in der NP-Menge (die gleich schwer oder leichter sind als die Probleme in der NP-vollständigen Menge) durch deterministisch polynomielle Laufzeit begrenzt, wodurch die P-Menge über die NP-Menge erweitert wird, was zu P=NP führt.

Bitte lassen Sie mich wissen, wenn ich einen Fehler gemacht habe.

Answer 2

Die obigen Definitionen für NP-komplette Probleme sind korrekt, aber ich dachte, ich könnte ein Loblied auf ihre philosophische Bedeutung singen, da sich noch niemand mit diesem Thema beschäftigt hat.

Fast alle komplexen Probleme, mit denen Sie konfrontiert werden, sind NP-vollständig. Diese Klasse hat etwas sehr Grundsätzliches an sich, das sich rechnerisch von leicht lösbaren Problemen zu unterscheiden scheint. Sie haben sozusagen ihren eigenen Geschmack, und es ist nicht schwer, sie zu erkennen. Das bedeutet im Grunde, dass jeder einigermaßen komplexe Algorithmus für Sie nicht exakt lösbar ist - Planen, Optimieren, Packen, Abdecken usw.

Aber es ist noch nicht alles verloren, wenn Sie auf ein Problem stoßen, das NP Complete heißt. Es gibt ein weites und sehr technisches Gebiet, auf dem man sich mit Approximationsalgorithmen beschäftigt, die Ihnen Garantien dafür geben, dass Sie nahe an der Lösung eines NP-vollständigen Problems sind. Einige dieser Garantien sind unglaublich stark - zum Beispiel kann man für 3sat eine 7/8-Garantie durch einen wirklich offensichtlichen Algorithmus erhalten. Noch besser ist, dass es in der Realität einige sehr starke Heuristiken gibt, die sich dadurch auszeichnen, dass sie gute Antworten (aber keine Garantien!) für diese Probleme liefern.

Man beachte, dass zwei sehr berühmte Probleme - Graphenisomorphismus und Faktorisierung - nicht als P oder NP bekannt sind.

Answer 3

NP-Problem :-

1. NP-Probleme sind solche Probleme, die in nicht-deterministischer Polynomialzeit gelöst werden können.
2. Der nicht deterministische Algorithmus arbeitet in zwei Stufen.
3. Nicht-deterministisches Raten && Nicht-deterministische Überprüfung.

Art des Np-Problems

1. NP vollständig
2. NP Hart

NP Vollständiges Problem :-

1 Entscheidungsproblem A heißt NP-vollständig, wenn es die folgenden zwei Eigenschaften hat:-

1. Sie gehört zur Klasse NP.
2. Jedes andere NP-Problem kann in Polynomialzeit in P transformiert werden.

Einige Ex :-

• Knapsack-Problem
• Teilmengensummenproblem
• Problem der Scheitelpunktabdeckung

Answer 4

NP-komplette Probleme sind eine Menge von Problemen, zu denen jedes beliebige jedes andere NP-Problem in polynomieller Zeit reduziert werden kann und dessen Lösung noch in polynomieller Zeit verifiziert werden kann. Das heißt, jedes NP-Problem kann in ein beliebiges NP-komplettes Problem transformiert werden. - Informell gesehen ist ein NP-komplettes Problem ein NP-Problem, das mindestens so "hart" ist wie jedes andere Problem in NP.