Dopełnienie przytoczonego problemu obliczeniowego może zostać sformułowane w następujący sposób: Mając dany skończony zbiór liczb całkowitych, rozstrzygnąć, czy dowolny jego niepusty podzbiór ma niezerową sumę. Definicja bazująca na weryfikatorach nie wymaga istnienia żadnego łatwego do zweryfikowania świadka dla odpowiedzi negatywnej. Klasę problemów obliczeniowych z takimi świadkami nazywamy co-NP. Problemem otwartym jest czy dla dowolnego problemu obliczeniowego w klasie NP istnieją świadkowie odpowiedzi negatywnych, a zatem czy zawierają się one w co-NP.
Definicja bazująca na maszynach Turinga Następująca definicja jest równoważna definicji bazującej na weryfikatorach: Klasa złożoności NP jest zbiorem problemów decyzyjnych rozpoznawanych przez niedeterministyczną maszynę Turinga działającą w czasie wielomianowym (oznacza to, że jeśli słowo należy do języka to istnieje przebieg akceptujący – klasa co-NP jest zdefiniowana analogicznie w kategorii ścieżek odrzucających). Równoważność powyższej definicji z tą bazującą na weryfikatorach opiera się na fakcie, że niedeterministyczna maszyna Turinga można rozwiązać problem z klasy NP w czasie wielomianowym poprzez niedeterministyczny wybór świadka oraz symulację na nim weryfikatora.