NP-Komplexität verstehen: Definition und Beispiele

NP steht für „Nondeterministic Polynomial Time“. Es handelt sich um eine Komplexitätsklasse, die sich auf die Zeit bezieht, die zur Lösung eines Problems erforderlich ist. In NP kann die Laufzeit eines Algorithmus polynomisch in der Grö+e der Eingabe sein, sie kann aber auch nichtdeterministisch sein, was bedeutet, dass die Laufzeit je nach der vom Algorithmus gewählten spezifischen Lösung variieren kann.

Mit anderen Worten, NP ist a Klasse von Problemen, die in polynomieller Zeit auf einer nichtdeterministischen Maschine gelöst werden können. Eine nichtdeterministische Maschine ist eine Maschine, die alle möglichen Lösungen für ein Problem parallel ausprobieren kann und die erste akzeptiert, die funktioniert. Dadurch kann die Maschine einige Probleme viel schneller lösen als eine deterministische Maschine, die jeweils nur eine Lösung ausprobieren kann.

Einige Beispiele für Probleme in NP sind:

* Das Problem des Handlungsreisenden (angegeben eine Liste von Städten und ihren paarweisen Entfernungen, Finden Sie die kürzestmögliche Route, die jede Stadt genau einmal besucht)
* Das Rucksackproblem (bestimmen Sie anhand einer Reihe von Gegenständen und deren Gewichten und Werten die Teilmenge der Gegenstände, die in einen Rucksack mit begrenzter Kapazität aufgenommen werden sollen, der den Gesamtwert maximiert)
* Das boolesche Erfüllbarkeitsproblem (bestimmen Sie bei einer gegebenen Menge boolescher Variablen und ihrer Einschränkungen, ob es eine Wertezuweisung zu den Variablen gibt, die alle Einschränkungen erfüllt). Die NP-Komplexitätsklasse ist wichtig, weil sie viele Probleme enthält, die in Polynomen schwer zu lösen sind Zeit, kann aber schnell von einer deterministischen Maschine überprüft werden. Das bedeutet, dass ein Algorithmus, auch wenn er möglicherweise nicht in der Lage ist, eine Lösung in polynomieller Zeit zu finden, dennoch nützlich sein kann, wenn er eine vorgeschlagene Lösung schnell verifizieren kann.