Należą do nich:
Klasa złożoności Model obliczeń Ograniczenie zasobów DTIME(f(n)) Deterministyczna maszyna Turinga Czas f(n) P Deterministyczna maszyna Turinga Czas poly(n) EXPTIME Deterministyczna maszyna Turinga Czas 2poly(n) NTIME(f(n)) Niedeterministyczna maszyna Turinga Czas f(n) NP Niedeterministyczna maszyna Turinga Czas poly(n) NEXPTIME Niedeterministyczna maszyna Turinga Czas 2poly(n) DSPACE(f(n)) Deterministyczna maszyna Turinga Miejsce f(n) L Deterministyczna maszyna Turinga Miejsce O(log n) PSPACE Deterministyczna maszyna Turinga Miejsce poly(n) EXPSPACE Deterministyczna maszyna Turinga Miejsce 2poly(n) NSPACE(f(n)) Niedeterministyczna maszyna Turinga Miejsce f(n) NL Niedeterministyczna maszyna Turinga Miejsce O(log n) NPSPACE Niedeterministyczna maszyna Turinga Miejsce poly(n) NEXPSPACE Niedeterministyczna maszyna Turinga Miejsce 2poly(n)
Z twierdzenia Savitcha wynika, że PSPACE = NPSPACE i EXPSPACE = NEXPSPACE.
Klasa NP Do tej klasy należą wszystkie problemy decyzyjne, które rozwiązuje niedeterministyczny algorytm wielomianowy (ang. non-deterministic polynomial).