Was sind P- und NP-Probleme?

Computeralgorithmen benötigen eine gewisse Zeit, um das ihnen gestellte Problem zu lösen. Im Allgemeinen können Sie anhand der Anzahl der Elemente, die er verarbeiten muss, grob abschätzen, wie lange ein Algorithmus benötigt. Informatiker nennen die Anzahl der Elemente  N .

Da einige Algorithmen mehr oder weniger effizient sind als andere, könnte die Zeit, die sie zum Abschluss benötigen, mit  N ,  N ² ,  N ³ usw. zusammenhängen. Wichtig ist jedoch, dass der Exponent eine Konstante ist – er ist 1 oder 2 usw. Wenn dies der Fall ist, wird ein Algorithmus in polynomieller Zeit oder  P abgeschlossen .

Leider funktionieren nicht alle Probleme auf diese Weise. Das Lösen einiger Probleme kann einen Algorithmus eine Zeitdauer benötigen, die proportional zu 2 ^N , 3 ^N usw. ist. In diesem Fall ist  N  der Exponent, was bedeutet, dass jedes Element, mit dem der Algorithmus umgehen muss, seine Komplexität exponentiell erhöht. In diesem Fall kann der Algorithmus in exponentieller Zeit oder  NP  (was eigentlich für nichtdeterministische polynomielle Zeit steht) abgeschlossen werden.

Der Unterschied zwischen diesen beiden kann enorm sein. Wenn ein  P-  Algorithmus 100 Elemente hat und seine Zeit bis zum Abschluss der Arbeit proportional zu  N ^{3 ist} , dann wird er sein Problem in etwa 3 Stunden lösen. Wenn es sich jedoch um einen  NP-  Algorithmus handelt und seine Fertigstellungszeit proportional zu 2 ^{N ist} , dauert es ungefähr 300 Trillionen Jahre.

Daher heißt ein Problem NP, wenn seine Lösung in polynomieller Zeit erraten und verifiziert werden kann, und nichtdeterministisch bedeutet, dass keine bestimmte Regel befolgt wird, um die Schätzung vorzunehmen. Andererseits ist ein P-Problem ein Problem, das in polynomieller Zeit durch deterministische Algorithmen gelöst werden kann.

Fakten zu P-Problemen

• P-Probleme sind eine Menge von Problemen, die in polynomieller Zeit durch deterministische Algorithmen gelöst werden können.
• Das Problem gehört zur Klasse P, wenn es leicht ist, eine Lösung für das Problem zu finden.
• P Probleme können in polynomieller Zeit gelöst und verifiziert werden.
• P-Probleme sind Teilmengen von NP-Problemen.
• Es ist nicht bekannt, ob P=NP ist. In NP sind jedoch viele Probleme mit der Eigenschaft bekannt, dass, wenn sie zu P gehören, P = NP bewiesen werden kann.
• Alle P-Probleme sind deterministischer Natur.
• Beispiel: Selektionssortierung, lineare Suche

Fakten zu Problemen der NP-Klasse

• NP-Probleme sind die Probleme, die in nichtdeterministischer polynomialer Zeit gelöst werden können.
• Das Problem gehört zu NP, wenn es leicht ist, eine Lösung zu überprüfen, die möglicherweise sehr mühsam zu finden war.
• Die Lösung von NP-Problemen kann nicht in polynomieller Zeit erhalten werden, aber wenn die Lösung gegeben ist, kann sie in polynomieller Zeit verifiziert werden.
• Falls P≠NP, gibt es Probleme in NP, die weder in P noch in NP-vollständig sind.
• NP-Probleme sind Obermengen von P-Problemen.
• Alle NP-Probleme sind nicht deterministischer Natur.
• Beispiel TSP, Rucksackproblem.

Lesen Sie auch : Unterschied zwischen Prims und Kruskals Algorithmus

Unterschied zwischen P-Problemen und NP-Problemen in Tabellenform

P PROBLEME	NP-PROBLEME
P-Probleme sind eine Menge von Problemen, die in polynomieller Zeit durch deterministische Algorithmen gelöst werden können.	NP-Probleme sind die Probleme, die in nichtdeterministischer polynomialer Zeit gelöst werden können.
Das Problem gehört zur Klasse P, wenn es leicht ist, eine Lösung für das Problem zu finden.	Das Problem gehört zu NP, wenn es leicht ist, eine Lösung zu überprüfen, die möglicherweise sehr mühsam zu finden war.
P Probleme können in polynomieller Zeit gelöst und verifiziert werden.	Die Lösung von NP-Problemen kann nicht in polynomieller Zeit erhalten werden, aber wenn die Lösung gegeben ist, kann sie in polynomieller Zeit verifiziert werden.
P-Probleme sind Teilmengen von NP-Problemen.	NP-Probleme sind Obermengen von P-Problemen.
Es ist nicht bekannt, ob P=NP ist. In NP sind jedoch viele Probleme mit der Eigenschaft bekannt, dass, wenn sie zu P gehören, P = NP bewiesen werden kann.	Falls P≠NP, gibt es Probleme in NP, die weder in P noch in NP-vollständig sind.
Alle P-Probleme sind deterministischer Natur.	Alle NP-Probleme sind nicht deterministischer Natur.
Auswahlsortierung, lineare Suche	TSP, Rucksackproblem.

Lesen Sie auch: Unterschied zwischen NP Hard und NP Complete Problem