Samo pytanie P vs NP dotyczy problemów decyzyjnych, czyli takich z odpowiedzią „tak” albo „nie”. W teorii złożoności bada się jednak również problemy liczenia rozwiązań. Klasa obejmuje zadania, w których trzeba policzyć liczbę certyfikatów spełniających warunek. Leslie Valiant pokazał, że takie problemy mogą być bardzo trudne nawet wtedy, gdy samo stwierdzenie istnienia rozwiązania jest łatwe. Z klasycznym pytaniem P vs NP wiążą się także wyniki o zliczaniu i aproksymacji, w tym twierdzenie Tody, wiążące klasę z hierarchią wielomianową, oraz twierdzenie PCP, które precyzuje trudność znajdowania rozwiązań bliskich optymalnym.
Część pokrewnych problemów wykracza poza klasyczny model deterministycznej maszyny Turinga używany w definicjach P i NP. W szczególności obliczenia losowe i kwantowe prowadzą do osobnych klas złożoności. Nie są one po prostu wariantem pytania P vs NP, lecz pokazują, że pojęcie efektywnego obliczania zależy także od przyjętego modelu. Obliczenia losowe opisuje m.in. klasa , a standardowym punktem odniesienia dla obliczeń kwantowych jest klasa BQP, obejmująca problemy rozwiązywalne przez komputer kwantowy z ograniczonym prawdopodobieństwem błędu.