Klasy złożoności

27. narysowad zależności pomiędzy problemami P, NP, NPC (oraz wyjaśnid, co znaczą)
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.