Teoria

Question 1

P, NP, coNP, NPcom, NP trudny

Answer 1

P - problem decyzyjny rozstrzygalny w czasie wiel.
NP - problem weryfikowalny w czasie wiel.
NPcom - problem decyzyjny, który można zredukować do NP w czasie wielomianowym
NP-trudny - problem decyzyjny co najmniej tak trudny jak każdy w NP

Pcom = NP i coNP
NPcom = NP i NP-trudny