Laufzeit und Platz-komplexitätsklasen

Übersicht

LogSpace $\subseteq$ NLogSpace $\subseteq$ P-Time $\subseteq$ NP-Time $\subseteq$ P-Space = NP-Space $\subseteq$ Exp-Time

Laufzeit

P-Time
NP-Time
NP-schwere Probleme
NP-vollständige Probleme
Exp-Time

Funktionen

FP-Time
FExp-Time

siehe
Platzkomplexitätsklassen