Informatik

Was ist die Komplexitätsklasse EXP?

EXP enthält Entscheidungsprobleme, die deterministisch in exponentieller Zeit lösbar sind, z.B. $2^{p(n)}$ für ein Polynom $p$.

Bekannt: $P\subseteq NP\subseteq PSPACE\subseteq EXP$.