Klassen av valgproblemer som lar seg løse på en (klassisk) Turingmaskin med polynomt minne (men ubegrenset tid—dog hvis jeg husker rett så kan ikke tid utover eksponentiell utnyttes til å løse ytterligere problemer på polynomt minne, slik at [[PSPACE]] $\subseteq$ [[EXP]]).