P np np-complete np-hard

(c) Behnam Esfahbod, CC BY-SA 3.0

Autor/Urheber:

Behnam Esfahbod

Shortlink:

https://dewiki.de/b/2cce6

Quelle:

Wikimedia Commons

Größe:

800 x 500 Pixel (13399 Bytes)

Beschreibung:

Euler diagram for P, NP, NP-Complete, and NP-Hard set of problems.

Lizenz:

CC BY-SA 3.0

Bild teilen:

         

Weitere Informationen zur Lizenz des Bildes finden Sie hier. Letzte Aktualisierung: Sat, 03 Feb 2024 00:26:55 GMT

Relevante Bilder

(c) Booyabazooka, CC BY-SA 3.0

Relevante Artikel

In der Informatik bezeichnet man ein Problem als NP-vollständig, wenn es zu den schwierigsten Problemen in der Klasse NP gehört, also sowohl in NP liegt als auch NP-schwer ist. Dies bedeutet umgangssprachlich, dass es sich vermutlich nicht effizient lösen lässt. .. weiterlesen

NP-Schwere bezeichnet die Eigenschaft eines algorithmischen Problems, mindestens so schwer lösbar zu sein wie die Probleme der Klasse NP. .. weiterlesen

Das P-NP-Problem ist ein ungelöstes Problem der Komplexitätstheorie in der theoretischen Informatik. Dabei geht es um die Frage, ob die Menge der Probleme, die schnell lösbar sind, und die Menge der Probleme, bei denen man eine vorgeschlagene Lösung schnell auf Korrektheit überprüfen kann, identisch sind. Schnell lösbar bzw. prüfbar bedeutet hier, dass dafür ein Algorithmus existiert, dessen Rechenaufwand, abhängig von der Größe der Eingabe, durch eine Polynomfunktion beschränkt ist. Die Größe der Eingabe ist hier vereinfacht gesagt die Anzahl der Elemente, die dem Algorithmus eingegeben werden. Beim Sortieren von Karteikarten wäre dies zum Beispiel die Anzahl der Karteikarten. .. weiterlesen