Dla kontrastu samo rozpoznawanie liczb pierwszych ma deterministyczny algorytm wielomianowy dzięki wynikowi Agrawala, Kayala i Saxeny z 2004 roku. Dlatego faktoryzacja dobrze ilustruje, że problemy ważne kryptograficznie mogą znajdować się poza znanym podziałem na P i NP-zupełne.
Problemy trudniejsze i pokrewne Pytanie P vs NP nie oznacza, że wszystkie problemy obliczeniowe mieszczą się w jednej z tych dwóch klas. Z twierdzeń hierarchii czasowej wynika, że P jest właściwie zawarte w EXPTIME, więc istnieją problemy rozwiązywalne w czasie wykładniczym, których nie da się rozwiązać w czasie wielomianowym. W literaturze jako przykłady naturalnych problemów o bardzo wysokiej złożoności analizowano m.in. uogólnione wersje gier planszowych oraz rozstrzyganie formuł arytmetyki Presburgera.
Z tego powodu problem P vs NP jest tylko jednym z pytań o granice efektywnego obliczania, choć pytaniem centralnym. Rozstrzygnięcie P ≠ NP oddzieliłoby P od części NP, ale nie wyczerpałoby klasyfikacji zadań jeszcze trudniejszych, problemów nierozstrzygalnych ani zadań liczbowych i aproksymacyjnych, które wymagają osobnych narzędzi teorii złożoności.