NP
NEXPTIMEは、非決定性チューリングマシンを使って指数時間で解ける問題のクラスであり、時間階層定理(英語版)より NP ⊊ NEXPTIME {\displaystyle {\textsf {NP}}\subsetneq {\textsf {NEXPTIME}}} が言える。また、EXPSPACEは、決定性チューリングマシンの指数サイズの領域を使って解ける問題のクラスであり、領域階層定理(英語版)より NP ⊊ EXPSPACE {\displaystyle {\textsf {NP}}\subsetneq {\textsf {EXPSPACE}}} が言える。
NP完全とNP困難は、NPの完全問題と困難問題のクラスである。直感的には、NPに属する任意の問題と少なくとも同じくらい難しい問題をNP困難であるといい、そのうちNPに属するものをNP完全問題という。これらの概念は正確には多項式時間帰着を使って定義する。充足可能性問題がNP完全に属することが知られている(クック–レビンの定理(英語版))。NP完全問題の1つでも P に属することが証明できれば P=NP と言えるが、そのような問題は見つかっていない。