Klasa złożoności może być zamknięta na dopełnienie, jeśli dopełnienie każdego problemu w tej klasie należy do tej klasy. Ponieważ istnienie redukcja Turinga z każdego problemu do jego dopełnienia, każda klasa zamknięta na redukcje Turinga jest zamknięta na dopełnienie. Każda klasa zamknięta na dopełnienie jest równa swojej klasie dopełniającej. W szczególności wszystkie klasy deterministyczne DSPACE(f(n)) i DTIME(f(n)), dla wszystkich f(n), są zamknięte na dopełnienie, ponieważ można zawsze dodać ostatni krok do maszyny Turinga, który odwraca odpowiedź. Ta metoda nie działa dla niedeterministycznych klas, ponieważ, jeśli istnieją ścieżki obliczeń zarówno akceptujące jak i nieakceptujące, odwrócenie odpowiedzi na końcu każdego obliczenia nic nie zmienia – w obu przypadkach maszyna odpowiada akceptująco.
Wiele istotnych klas jest uważanych za różne od swoich dopełnień. W szczególności NP uważa się za różne od Co-NP, choć nie zostało to udowodnione.
Jednym z najbardziej zaskakujących rezultatów w teorii złożoności jest twierdzenie Immermana-Szelepcsényiego pokazujące, że wszystkie niedeterministyczne klasy pamięciowe NSPACE są zamknięte na dopełnienie.
Zobacz też asymptotyczne tempo wzrostu Kategoria:Teoria obliczeń