- Gruppierung vergleichbar schwieriger Algorithmen
- Üblichwerweise Zeit- und Platzbedarf, andere Ressourcen sind als Maß aber auch möglich
Definition: Zeitkomplexitätsklasse TIME
Sei
. Die Zeitkomplexitätsklasse enthält alle Sprachen, die von einer -DTM entschieden werden.
Definition: Komplexitätsklasse P
- Invariant gegenüber polynomialen Beschleunigungen/verlangsamungen
- Enthält TIME(1), TIME(log n), TIME(n log n), …
Warum diese Einteilung?
- Alle Polynomiellen Wachstumsarten bleiben berechenbar
Definition: Zeitkomplexitätsklasse NTIME
Äquivalent von TIME für nichtdeterministische Turing-Maschinen
Definition: Komplexitätsklasse NP
- NP bedeutet nicht dass es nicht-polynomial skalierend ist!
- Es bedeutet Nichtdeterministisch Polynomial skalierend!