Nie jest wiadome, czy NP jest zamknięte na dopełnienie (jest to tak zwany problem NP vs. co-NP).
Dlaczego niektóre problemy NP są trudne Ponieważ w klasie tej znajduje się wiele istotnych problemów, podjęte zostały intensywne prace nad znalezieniem algorytmów działających w czasie wielomianowym rozwiązujących problemy NP. Niemniej jednak, w klasie NP wciąż pozostało wiele problemów, dla których nie udało się opracować takich algorytmów i wydają się one wymagać superwielomianowego czasu obliczeń. Zagadnienie, czy wszystkie takie problemy da się rozwiązać w czasie wielomianowym jest jednym z najważniejszych pytań informatyki (jest to tak zwany problem P vs NP).
Ważnym dla tego problemu pojęciem jest klasa problemów NP-zupełnych, która jest podzbiorem NP i może być nieformalnie rozumiana jako zbiór „najtrudniejszych” problemów NP. Jeśli istnieje wielomianowy algorytm rozwiązujący pewien problem NP-zupełny, to dowolny problem NP można rozwiązać w czasie wielomianowym.