Dopełnienie – problem decyzyjny powstający po zamianie miejscami odpowiedzi tak i nie. Równoważnie, jeśli zdefiniujemy proces decyzyjny jako zbiór skończonych napisów, dopełnienie zbioru tych napisów nad ich alfabetem jest dopełnieniem problemu.
Przykładowo, jeśli rozważymy problem decyzyjny określania czy dana liczba jest liczbą pierwszą, to dopełnieniem tego problemu będzie określanie czy dana liczba jest liczbą złożoną.
Uogólniając tę operację na klasy złożoności obliczeniowej, możemy wprowadzić klasy będące dopełnieniem problemów w danej klasie. Jeśli pierwotna klasa nazywana jest C, jej klasa dopełniająca jest nazywana Co-C. Należy pamiętać, że nie jest ona dopełnieniem tej klasy jako zbioru problemów – dopełnienie takie zawiera zwykle znacznie więcej problemów.