Complexity classes (de)

(c) Booyabazooka, CC BY-SA 3.0

Shortlink:

https://www.dewiki.de/b/762e3

Quelle:

Wikimedia Commons

Größe:

414 x 255 Pixel (3345 Bytes)

Beschreibung:

German version of Image:Complexity classes.svg: Complexity classes P and NP

Lizenz:

CC BY-SA 3.0

Credit:

Image:Complexity classes.svg

Bild teilen:

         

Weitere Informationen zur Lizenz des Bildes finden Sie hier. Letzte Aktualisierung: Thu, 14 Mar 2024 09:08:51 GMT

Relevante Bilder

(c) Behnam Esfahbod, CC BY-SA 3.0

Relevante Artikel

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