Erinnern Sie sich, was ein NP-vollständiges Problem ist? Worin unterscheidet es sich von einfachem NP?

NP (nichtdeterministische polynomielle Zeit) ist eine Klasse von Problemen, bei denen die Lösung in polynomieller Zeit überprüft werden kann. Das heißt, wenn Sie einen Kandidaten für die Antwort haben, können Sie schnell überprüfen, ob er richtig ist oder nicht.

NP-vollständige Probleme sind eine Teilmenge von NP, die gleichzeitig die "schwierigsten" in dieser Klasse sind. Wenn jemand einen polynomiellen Algorithmus zur Lösung eines beliebigen NP-vollständigen Problems finden würde, könnten alle Probleme in NP in polynomieller Zeit gelöst werden.

Hauptunterschied:

• NP: Probleme, deren Lösungen schnell überprüft werden können.
• NP-vollständig: Probleme in NP, auf die jedes andere NP-Problem reduziert werden kann (d.h., sie sind die "kompliziertesten" in NP).

Beispiel: Das Problem des maximalen Cliquen-Subgraphen in einem Graphen ist NP-vollständig, und das Überprüfungsproblem, ob eine Teilmenge von Elementen eine Summe zu einer vorgegebenen Zahl bildet, ist in NP.