Plus précisément, c`est l`ensemble des problèmes de décision qui peuvent se résoudre sur une machine de Turing non déterministe en temps O(2p(n)) avec certains polynôme « p »(n), et un espace mémoire illimité. C`est donc la version non-déterministe de EXPTIME.