Komplexitätsklassen – P, NP und NP vollständig

Die Komplexitätsklassen P und NP sind jeweils eine Menge aus Problemen. In der Klasse P befinden sich die Probleme, die in polynomieller Zeit lösbar sind, es sind Sozusagen „leichte“ Probleme. Das heißt für diese Art von Problemen existiert ein Algorithmus, der in polynomieller Zeit (also in naher Zukunft) eine Lösung findet.

In der Klasse NP befinden sich die Probleme, bei denen in polynomieller Zeit geprüft werden kann, ob es eine Lösung gibt oder nicht. Man nennt sie auch nichtdeterministische polynomielle Probleme. Das heißt, in dieser Klasse befinden sich alle Probleme, über die man eine Aussagen treffen kann, ob es eine Lösung für dieses Problem gibt oder nicht. Jedoch ist es (noch) nicht möglich, diese Probleme zu lösen. Jedes Problem in P befindet sich übrigens auch automatisch in der Klasse NP. Zusätzlich existieren in NP Probleme, über die man nicht einmal aussagen kann, dass es eine Lösung gibt, das heißt für solche Probleme existiert auch kein Algorithmus zur Berechnung der Lösung. Diese Art von Problemen befinden sich in NP-vollständig.

Zusammenfassung
Komplexitätsklassen - P, NP und NP vollständig
Artikeltitel
Komplexitätsklassen - P, NP und NP vollständig
Beschreibung
Eine kurze Übersicht über die Komplexitätsklassen - P, NP und NP vollständig und was diese eigentlich bedeuten.
Autor

Kommentare

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert.

E-Mail-Benachrichtigung bei weiteren Kommentaren.
Auch möglich: Abo ohne Kommentar.

Diese Website verwendet Akismet, um Spam zu reduzieren. Erfahre mehr darüber, wie deine Kommentardaten verarbeitet werden .

Pin It on Pinterest

Durch die weitere Nutzung der Seite stimmst du der Verwendung von Cookies zu. Weitere Informationen

Die Cookie-Einstellungen auf dieser Website sind auf "Cookies zulassen" eingestellt, um das beste Surferlebnis zu ermöglichen. Wenn du diese Website ohne Änderung der Cookie-Einstellungen verwendest oder auf "Akzeptieren" klickst, erklärst du sich damit einverstanden.

Schließen