KLASY ZŁOŻONOŚCI

P – klasa problemów rozwiązywalnych za pomocą algorytmu deterministyczne w czasie wielomianowym
NP. – klasa problemów rozwiązywalnych za pomocą algorytmu niedeterministycznego w czasie
wielomianowym
coNP – klasa problemów komplementarnych do NP.
PSPACE – klasa problemów rozwiązywalnych za pomocą algorytmu deterministycznego o
wielomianowej złożoności pamięciowej
EXPTIME – klasa problemów rozwiązywalnych za pomocą algorytmu deterministycznego o wykładniczej
złożoności czasowej
EXPSPACE – klasa problemów rozwiązywalnych za pomocą algorytmu deterministycznego o
wykładniczej złożoności pamięciowej
Klasa NPC problemów NP-zupełnych (NP-Complete)
Klasa problemów najtrudniejszych obliczeniowo w NP.