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

Schreibe einen Kommentar

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

Notify me of followup comments via e-mail. You can also subscribe without commenting.