EXP

Die Klasse EXP ist die Menge aller Probleme $P$ ,
die auf Eingaben der Größe $n$ in Zeit

2^{O (n^{d})}

für ein festes $d \geq 1$ gelöst werden können.

Beispiel:

3 -COL \in EXP .