Berechnungskomplexität

Konzepte der Informatik

Pritesh Patel

Computer Scientist & Data Scientist for over 20 years

Komplexitätsklassen

Komplexitätsklassen

Eine Animation, die den gesamten Komplexitätsraum zeigt

Ein Bild, das den Problemraum P zeigt

Komplexitätsklasse -->	P (Polynomzeit)
Bedeutung	Schnell und effizient lösbar
Beispiel	Eine Liste sortieren
Analogie	„Dokumente alphabetisch ablegen“
Kernaussage	In Rechenbegriffen „einfach“

¹ https://www.baeldung.com/cs/p-np-np-complete-np-hard

Ein Bild, das den Problemraum P und NP zeigt

Komplexitätsklasse -->	NP (Nichtdeterministische Polynomzeit)
Bedeutung	Lösungen prüfbar, neue Lösung schwer zu finden
Beispiel	Sudoku-Lösung auf Korrektheit prüfen
Analogie	„Ein bestimmtes Dokument mit fehlenden Infos suchen“
Kernaussage	Prüfen ist „einfach“, Finden neuer Lösungen ist schwer

¹ https://www.baeldung.com/cs/p-np-np-complete-np-hard

Ein Bild, das den Problemraum P, NP und NP-vollständig zeigt

Komplexitätsklasse -->	NP-vollständig
Bedeutung	Schwierigste in NP. Besonders, weil löst alle NP
Beispiel	Travelling-Salesman-Problem
Analogie	„Komplexes Puzzle: leicht zu prüfen, schwer zu lösen“
Kernaussage	Kein effizienter Algorithmus bekannt. Falls doch, löst er alle NP

¹ https://www.baeldung.com/cs/p-np-np-complete-np-hard

Ein Bild, das den Problemraum P, NP, NP-vollständig und NP-schwer zeigt

Komplexitätsklasse -->	NP-schwer
Bedeutung	So schwer wie NP-vollständig oder schwerer
Beispiel	Optimale Planung mit komplexen Abhängigkeiten, nicht verifizierbar
Analogie	„Optimalen Termin mit vielen Constraints finden, nicht schnell prüfbar“
Kernaussage	Praktisch evtl. unlösbar

¹ https://www.baeldung.com/cs/p-np-np-complete-np-hard

Ein Diagramm mit der alten Forschungsfrage: Gilt P=NP?

Konzepte der Informatik